二叉树

1. 遍历二叉树

有如下树形结构的数据：

let tree = {
    value: 0,
    children: [{
        value: 11,
        children: [{
            value: 21,
            children: [{
                value: 31,
                children: []
            }, {
                value: 32,
                children: []
            }, {
                value: 33,
                children: []
            }]
        }, {
            value: 22,
            children: []
        }]
    }, {
        value: 12,
        children: [{
            value: 23,
            children: []
        }, {
            value: 24,
            children: []
        }]
    }, {
        value: 13,
        children: []
    }]
}

1.1 递归遍历

function recursiveTraverse (node, action) {
    if (!node || !node.children) { return }
    action(node.value)
    node.children.forEach(function(item, index) {
        recursiveTraverse(item, action)
    })
}
recursiveTraverse(tree, console.log)

1.2 栈实现 — 非递归深度优先（DFS）遍历

function nonRecursiveDepthFirstTraversal (node, action) {
    if (!node || !node.children) { return }
    // 借助一个栈
    let _stack = []
    _stack.push(node)
    while (_stack.length) {
        // 推出栈顶元素
        let _curNode = _stack.pop()
        action(_curNode.value)
        // 将子节点依次放入到栈顶
        if (_curNode.children.length) {
            // 将推出栈顶元素的子节点依次放入到栈顶，每次先遍历后进栈的元素
            _stack = _curNode.children.concat(_stack)
        }
    }
}
nonRecursiveDepthFirstTraversal(tree, console.log)

栈是一种遵从后进先出、先进后出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾，称作栈顶。另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。

1.3 队列实现 — 非递归广度优先（BFS）遍历

function nonRecursiveWidthFirstTraversal (node, action) {
    if (!node || !node.children) { return }
    // 借助一个队列
    let _queue = []
    _queue.push(node)
    while (_queue.length) {
        // 推出队头元素
        let _curNode = _queue.shift()
        action(_curNode.value)
        // 将子节点依次推入队列中
        if (_curNode.children.length) {
            _queue = _queue.concat(_curNode.children)
        }
    }
}
nonRecursiveWidthFirstTraversal(tree, console.log)

队列遵循的是先进先出、后进后出(FIFO)原则的一组有序的项。队列从尾部添加新元素，并从顶部移除元素，最新添加的元素必须排列在队列的末尾。

2. 二叉搜索树

2.1 定义

二叉搜索树又称为排序二叉树，为二叉树的一种类型，其特点为：

1. 节点分为左右子树；
2. 在不为空的情况下，左子树子节点的值都小于父节点的值；
3. 在不为空的情况下，右子树子节点的值都大于父节点的值；
4. 每个节点的左右子树都按照上述规则排序。

如图：

2.2 数据结构

• 节点用对象来描述，节点特性用对象属性来描述

class Node {
  constructor(key) {
    this.key = key  // 节点值
    this.left = null  // 左指针
    this.right = null  // 右指针
  }
}

• 二叉树结构用对象来描述。

class BinaryTree {
  constructor() {
    this.root = null;  // 根节点
  }
  insert(key) {
    const newNode = new Node(key)
    if (this.root === null) {
      this.root = newNode
      return
    }
    this.insertNode(this.root, newNode)
  }
  insertNode(root, newNode) {
    if (!newNode) return
    let tail = root
    // 找到可以插入的节点位置
    while (tail) {
      if (newNode.key > tail.key) {
        if (tail.right) {
          tail = tail.right
        } else {
          tail.right = newNode
          return tail
        }        
      } else {
        if (tail.left) {
          tail = tail.left
        } else {
          tail.left = newNode
          return tail
        }
      }
    }
  }
}

• 具体用法：

// 实例化二叉树
const binaryTree = new BinaryTree()
// key值
const keys = [19, 8, 15, 24, 45, 12, 5]
// 生成排序二叉树
keys.forEach(key => binaryTree.insert(key))

• 结果：

2.3 遍历

traversal: [trəˈvərs(ə)l]遍历

二叉树遍历分为：

• 前序遍历：根-左-右
• 中序遍历：左-根-右
• 后序遍历：左-右-根

以上面一个例子来说：

• 前序遍历的结果：[19, 8, 5, 15, 12, 24, 45]
• 中序遍历的结果：[5, 8, 12, 15, 19, 24, 45]
• 后序遍历的结果：[5, 12, 15, 8, 45, 24, 19]

2.3.1 前序遍历

思路：

1. 取跟节点为目标节点，开始遍历；
2. 访问目标节点；
3. 左孩子入栈，直至左孩子为空的节点；
4. 节点出栈，以右孩子为目标节点，再依次执行2、3、4。

function preorderTraversal(root) {
  let res = []
  if (!root) return res
  let stack = []
  let tail = root
  while(tail || stack.length) {
    if (tail) {
      res.push(tail.key)
      stack.push(tail)
      tail = tail.left
    } else {
      let node = stack.pop()
      tail = node.right
    }
  }
  return res
}

2.3.3 中序遍历

中序遍历又叫升序遍历，从小到大排列

思路：

1. 取跟节点为目标节点，开始遍历；
2. 左孩子入栈，直至左孩子为空的节点；
3. 节点出栈，访问该节点；
4. 以右孩子为目标节点，再依次执行2、3、4。

function inorderTraversal(root) {
  let res = []
  if (!root) return res
  let stack = []
  let tail = root
  while (tail || stack.length) {
    if (tail) {
      stack.push(tail)
      tail = tail.left
    } else {
      let node = stack.pop()
      res.push(node.key)
      tail = node.right
    }
  }
  return res
}

2.3.4 后序遍历

思路：

1. 取跟节点为目标节点，开始遍历；
2. 右孩子入栈，直至右孩子为空的节点；
3. 节点出栈，访问该节点；
4. 以左孩子为目标节点，再依次执行2、3、4。

function postorderTraversal(root) {
  let res = []
  if (!root) return res
  let stack = []
  let tail = root
  while (tail || stack.length) {
    if (tail) {
      res.unshift(tail.key)
      stack.push(tail)
      tail = tail.right
    } else {
      let node = stack.pop()
      tail = node.left
    }
  }
  return res
}

2.4 查找

2.4.1 查找最大值

根据排序二叉树的特点，右子树的值都大于父节点的值。只需要进入节点的右子树查找，当某个节点的右子树为空时，该节点就是最大值节点。

function searchMaxNode(root) {
  if (!root) return null
  let tail = root
  while (tail.right) {
    tail = tail.right
  }
  return tail.key
}

2.4.2 查找最小值

根据排序二叉树的特点，左子树的值都小于父节点的值。只需要进入节点的左子树查找，当某个节点的左子树为空时，该节点就是最小值节点。

function searchMinNode(root) {
  if (!root) return null
  let tail = root
  while (tail.left) {
    tail = tail.left
  }
  return tail.key
}

2.4.3 查找给定值

根据排序二叉树的特点，比较给定值与节点值，小于时进入节点左子树。大于时进入节点右子树。等于时返回真。层层对比，最后如果子树为空，则表示没有找到。

function searchNode(root, key) {
  if (!root || !key) return false
  let tail = root
  while (tail) {
    if (key > tail.key) {
      tail = tail.right
    } else if (key < tail.key) {
      tail = tail.left
    } else if (key === tail.key) {
      return true
    }
  }
  return false
}

2.5 删除

2.5.1 删除指定节点

删除节点分为以下几张情况：

• 被删除节点为叶子节点时；

思路：将该叶子节点的父节点指向的子节点的引用值设为空。

• 被删除节点仅有一个子树；

思路：将该节点的父节点指向该节点的引用改成指向该节点的子节点。

• 被删除节点有两个子树。

思路：从待删除节点的右子树找节点值最小的节点A，替换待删除节点，并删除节点A。

function removeNode(root, key) {
  if (!root) return false
  let tail = root
  // 存储父节点
  let parent = null
  while (tail) {
    if (key > tail.key) {
      parent = tail
      tail = tail.right
    } else if (key < tail.key) {
      parent = tail
      tail = tail.left
    } else if (key === tail.key) {
      if (!tail.left && !tail.right) {
        // 被删除节点为叶子节点
        if (parent.left && parent.left.key === tail.key) {
          parent.left = null
        } else {
          parent.right = null
        }
      } else if (!(tail.left && tail.right)) {
        // 被删除节点仅有一个子树
        if (tail.left) {
          if (parent.left && parent.left.key === tail.key) {
            parent.left = tail.left
          } else {
            parent.right = tail.left
          }
        } else {
          if (parent.left && parent.left.key === tail.key) {
            parent.left = tail.right
          } else {
            parent.right = tail.right
          }
        }
      } else {
        // 被删除节点有两个子树
        let minKey = searchMinNode(tail.right)
        tail.key = minKey
        removeNode(tail.right, minKey)
      }
      break
    }
  }
}

3. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数；
• 节点的右子树只包含大于当前节点的数；
• 所有左子树和右子树自身必须也是二叉搜索树。

示例1：

输入:
    2
   / \
  1   3
输出: true

示例2：

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5, 1, 4, null, null, 3, 6]。根节点的值为 5 ，但是其右子节点值为 4 。

解题：

• 解法：二叉搜索树中序遍历
• 时间复杂度：O(n)
• 空间复杂度：O(1)

中序遍历又叫升序遍历，所以仅需判断当前出栈的节点与上一个节点的大小，小于则不符合。

function validBST(root) {
  if (!root) return false
  let stack = []
  let tail = root
  let lastNodeKey = null
  while (tail || stack.length) {
    if (tail) {
      stack.push(tail)
      tail = tail.left
    } else {
      let node = stack.pop()
      if (lastNodeKey != null && lastNodeKey >= node.key) {
        return false
      }
      lastNodeKey = node.key
      tail = node.right
    }
  }
}

4. 验证平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例1：

给定二叉树 [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例2：

给定二叉树 [1,2,2,3,3,null,null,4,4]
       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

解题思路：

• 后续遍历二叉树
• 在遍历二叉树每个节点前都会遍历其左右子树
• 比较左右子树的深度，若差值大于1则返回一个标记，-1表示当前子树不平衡
• 左右子树有一个不是平衡的，或左右子树差值大于1，则整课树不平衡
• 若左右子树平衡，返回当前树的深度（左右子树的深度最大值+1）

function IsBalanced_Solution(pRoot) {
  return balanced(pRoot) != -1
}
function balanced(node) {
  if(!node) return 0
  // 计算左子树的深度
  const left = balanced(node.left)
  // 计算右子树的深度
  const right = balanced(node.right)
  if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
    return -1
  }
  return Math.max(left, right) + 1
}