Neil.
· 约 1 分钟

数算再回顾（二）二叉树常见算法

前言

数（据结构）算（法）再回顾，加深记忆抗遗忘。

前序遍历

144. 二叉树的前序遍历

基本规律：二叉树前序遍历结果一定是[root, left, right]

// 递归
var preorderTraversal = function (root) {
  if (!root) return [];

  const r1 = preorderTraversal(root.left);
  const r2 = preorderTraversal(root.right);

  return [root.val].concat(r1).concat(r2);
};
// 迭代
var preorderTraversal = function (root) {
  const stack = [];
  const result = [];

  while (root || stack.length) {
    // 沿左子树遍历
    while (root) {
      stack.push(root);
      result.push(root.val);
      root = root.left;
    }
    // 回到父节点
    const node = stack.pop();
    // 切换到右子树
    root = node.right;
  }

  return result;
};

中序遍历

94. 二叉树的中序遍历

基本规律：二叉树中序遍历结果一定是[left, root, right]

// 递归
var inorderTraversal = function (root) {
  if (!root) return [];

  const r1 = inorderTraversal(root.left);
  const r2 = inorderTraversal(root.right);

  return r1.concat([root.val]).concat(r2);
};
// 迭代
var inorderTraversal = function (root) {
  const stack = [];
  const result = [];

  while (root || stack.length) {
    // 沿左子树遍历
    while (root) {
      stack.push(root);
      root = root.left;
    }
    // 回溯到父节点
    const node = stack.pop();
    result.push(node.val);
    // 切换到右子树
    root = node.right;
  }

  return result;
};

后序遍历

145. 二叉树的后序遍历

基本规律：二叉树后序遍历结果一定是[left, right, root]

// 递归
var postorderTraversal = function (root) {
  if (!root) return [];

  const r1 = postorderTraversal(root.left);
  const r2 = postorderTraversal(root.right);

  return r1.concat(r2).concat([root.val]);
};
// 迭代
var postorderTraversal = function (root) {
  const stack = [];
  const result = [];
  let prevTraversedNode = null;

  while (root || stack.length) {
    // 沿左子树遍历
    while (root) {
      stack.push(root);
      root = root.left;
    }

    // 回溯到父节点
    const node = stack.pop();
    if (!node.right || node.right === prevTraversedNode) {
      // 确定右子树不存在，或右子树已经访问过，再来访问该节点
      result.push(node.val);
      // 更新已访问节点为该节点
      prevTraversedNode = node;
    } else {
      // 切换到右子树
      stack.push(node);
      root = node.right;
    }
  }

  return result;
};

前中后序遍历总结

递归实现只需记住返回结果时的规律：

  1. 前：[root, left, right]
  2. 中：[left, root, right]
  3. 后：[left, right, root]

同理，该规律也可以用来解决这类经典问题：已知中序 + 前 or 后序遍历结果，重建二叉树；

迭代实现记住先左后右，然后注意何时取值；

  1. 前：沿左遍历时取值；
  2. 中：回溯到父节点时取值；
  3. 后：回溯到父节点时：
    1. 如果右子树不存在或已经遍历过，此时再取值；
    2. 如果右子树存在且没有遍历过，之前 pop 的节点要再 push 回去，因为此时还不能取值；

层序遍历

// 从根到叶
var levelOrder = function (root) {
  const queue = [root];
  const result = [];
  while (root && queue.length) {
    const layer = [];
    let len = queue.length;
    while (len) {
      const node = queue.pop();
      layer.push(node.val);
      node.left && queue.unshift(node.left);
      node.right && queue.unshift(node.right);
      len--;
    }
    result.push(layer);
  }

  return result;
};
// 从叶到根
var levelOrderBottom = function (root) {
  const queue = [root];
  const result = [];

  while (root && queue.length) {
    const layer = [];
    let len = queue.length;
    while (len) {
      const node = queue.pop();
      layer.push(node.val);
      node.left && queue.unshift(node.left);
      node.right && queue.unshift(node.right);
      len--;
    }

    result.push(layer);
  }

  return result.reverse();
};
// 交错层序
var zigzagLevelOrder = function (root) {
  const queue = [root];
  const result = [];
  let shouldReverse = false;

  while (root && queue.length) {
    let len = queue.length;
    const layer = [];
    while (len) {
      const node = queue.pop();
      layer.push(node.val);
      node.left && queue.unshift(node.left);
      node.right && queue.unshift(node.right);
      len--;
    }

    result.push(shouldReverse ? layer.reverse() : layer);
    shouldReverse = !shouldReverse;
  }

  return result;
};

根据遍历结果重建二叉树

此类问题只有两种：

  • 中序和前序遍历序列；
  • 中序和后序遍历序列；

原理是前中后序遍历所得序列符合固定规则，而且重点在于，任意子树对应的序列也符合该规则：

  1. 前：[root, left, right]
  2. 中：[left, root, right]
  3. 后：[left, right, root]

这也是数据结构考研题型中经常出现的一类问题，从上述规则可以总结出：

  1. 前序数组的首元素是根节点；
  2. 中序数组的根节点对应元素的左右两侧分别是左右子树；
  3. 后序数组的尾元素是根节点；

综上，通过前或后序确定根节点，通过中序确定左右子树节点个数，通过节点个数切分前或后序数组；

106 从中序与后序遍历序列构造二叉树

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
  // 结束条件
  if (inorder.length === 0) {
    return null;
  }
  if (inorder.length === 1) {
    return new TreeNode(inorder[0], null, null);
  }
  // 找到根节点
  const root = postorder[postorder.length - 1];
  const rootIndex = inorder.findIndex((v) => v === root);
  // 划分左右子树
  const leftInorder = inorder.slice(0, rootIndex);
  const rightInorder = inorder.slice(rootIndex + 1);
  const leftPostorder = postorder.slice(0, leftInorder.length);
  const rightPostorder = postorder.slice(
    leftInorder.length,
    postorder.length - 1
  );
  // 进入下一层递归调用，记录结果
  const leftChild = buildTree(leftInorder, leftPostorder);
  const rightChild = buildTree(rightInorder, rightPostorder);
  // 构建树结构并返回
  return new TreeNode(root, leftChild, rightChild);
}

105 从前序与中序遍历序列构造二叉树

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  // 结束条件
  if (inorder.length === 0) {
    return null;
  }
  if (inorder.length === 1) {
    return new TreeNode(inorder[0], null, null);
  }
  // 找到根节点
  const root = preorder[0];
  const rootIndexOfInorder = inorder.findIndex((v) => v === root);
  // 划分左右子树
  const leftInorder = inorder.slice(0, rootIndexOfInorder);
  const rightInorder = inorder.slice(rootIndexOfInorder + 1);
  const leftPreorder = preorder.slice(1, 1 + leftInorder.length);
  const rightPreorder = preorder.slice(1 + leftInorder.length);
  // 进入下一层递归调用，记录结果
  const leftChild = buildTree(leftPreorder, leftInorder);
  const rightChild = buildTree(rightPreorder, rightInorder);
  // 构建树结构并返回
  return new TreeNode(root, leftChild, rightChild);
}

注意 Array.prototype.slice(start, end) 的用法即可，切分出的数组不包含下标为 end 的元素，且 end 默认为数组的长度。