重建二叉树

问题

给定二叉树的前序遍历和中序遍历结果，重建该二叉树。假设输入的前序遍历和中序遍历结果中都不含重复的数字。

例如：

• 前序遍历：[3, 9, 20, 15, 7]
• 中序遍历：[9, 3, 15, 20, 7]

重建出的二叉树：

    3
   / \
  9  20
    /  \
   15   7

解答

思路

• 前序遍历：根 → 左 → 右，第一个元素是根节点
• 中序遍历：左 → 根 → 右，根节点左边是左子树，右边是右子树

通过前序找到根节点，再在中序中定位根节点位置，从而划分左右子树，递归构建。

实现

// 二叉树节点
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

/**
 * 根据前序和中序遍历重建二叉树
 * @param {number[]} preorder - 前序遍历结果
 * @param {number[]} inorder - 中序遍历结果
 * @return {TreeNode}
 */
function buildTree(preorder, inorder) {
  // 构建中序遍历的值到索引的映射，加速查找
  const inorderMap = new Map();
  inorder.forEach((val, index) => inorderMap.set(val, index));

  // 递归构建
  function build(preStart, preEnd, inStart, inEnd) {
    // 递归终止条件
    if (preStart > preEnd) return null;

    // 前序遍历的第一个元素是根节点
    const rootVal = preorder[preStart];
    const root = new TreeNode(rootVal);

    // 在中序遍历中找到根节点位置
    const rootIndex = inorderMap.get(rootVal);

    // 计算左子树的节点数量
    const leftSize = rootIndex - inStart;

    // 递归构建左子树
    // 前序：[preStart+1, preStart+leftSize]
    // 中序：[inStart, rootIndex-1]
    root.left = build(
      preStart + 1,
      preStart + leftSize,
      inStart,
      rootIndex - 1
    );

    // 递归构建右子树
    // 前序：[preStart+leftSize+1, preEnd]
    // 中序：[rootIndex+1, inEnd]
    root.right = build(
      preStart + leftSize + 1,
      preEnd,
      rootIndex + 1,
      inEnd
    );

    return root;
  }

  return build(0, preorder.length - 1, 0, inorder.length - 1);
}

测试

// 测试
const preorder = [3, 9, 20, 15, 7];
const inorder = [9, 3, 15, 20, 7];

const tree = buildTree(preorder, inorder);

// 验证：层序遍历输出
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    result.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

console.log(levelOrder(tree)); // [3, 9, 20, 15, 7]

简洁版本

function buildTree(preorder, inorder) {
  if (!preorder.length) return null;

  const rootVal = preorder[0];
  const root = new TreeNode(rootVal);
  const mid = inorder.indexOf(rootVal);

  root.left = buildTree(
    preorder.slice(1, mid + 1),
    inorder.slice(0, mid)
  );
  root.right = buildTree(
    preorder.slice(mid + 1),
    inorder.slice(mid + 1)
  );

  return root;
}

关键点

• 前序遍历第一个元素是根节点，中序遍历中根节点左边是左子树、右边是右子树
• 用 Map 缓存中序遍历的索引，将查找从 O(n) 优化到 O(1)
• 通过索引划分避免 slice 创建新数组，降低空间复杂度
• 时间复杂度 O(n)，空间复杂度 O(n)（Map + 递归栈）