二叉树的遍历与构建

二叉树的四种遍历方式：
二叉树的遍历，即按照某种次序依次访问二叉树中所有的结点，使得每个结点被依照次序进行访问且仅被访问一次。
四种遍历方式分别为：
深度优先：先序遍历、中序遍历、后序遍历
广度优先：层序遍历

• 以中序遍历为例：

中序遍历的递归实现

const inorderTraversal = (root) => {
    const res = [];
    const inorder = (root) => {
        if (root == null) {
            return;
        }
        inorder(root.left); // 先递归左子树
        res.push(root.val); // 将当前节点值推入res
        inorder(root.right); // 再递归右子树
    };
    inorder(root);
    return res;
};

中序遍历的迭代实现

const inorderTraversal = (root) => {
  const res = [];
  const stack = [];

  while (root) {        // 能压栈的左子节点都压进来
    stack.push(root);
    root = root.left;
  }
  while (stack.length) {
    let node = stack.pop(); // 栈顶的节点出栈
    res.push(node.val);     // 在压入右子树之前，处理它的数值部分（因为中序遍历）
    node = node.right;      // 获取它的右子树
    while (node) {          // 右子树存在，执行while循环    
      stack.push(node);     // 压入当前root
      node = node.left;     // 不断压入左子节点
    }
  }
  return res;
};

能够对二叉树进行遍历，同时也能依据遍历结果对二叉树进行重建

由前序遍历和中序遍历构建二叉树

let buildTree = (preorder, inorder) => {

  //当preorder和inorder均为空的时候说明已经到了空节点
  if (!preorder.length || !inorder.length) return null;

  //创建根节点 -> preorder[0]
  let node = new TreeNode(preorder[0]);

  //找到preoder[0]对应inorder中的位置
  let index = inorder.indexOf(preorder.shift());

  //左右子树递归
  node.left = buildTree(preorder, inorder.slice(0, index));
  node.right = buildTree(preorder, inorder.slice(index + 1));

  //返回根节点
  return node;
};