Description

算法步骤

核心思路： 利用前序遍历确定根节点，利用中序遍历确定左右子树的范围，通过递归构建二叉树。

关键步骤：

1. 前序遍历的第一个元素是根节点
2. 在中序遍历中找到根节点位置，划分左右子树
3. 递归构建左右子树

索引计算：

• 左子树前序遍历起始：preL + 1
• 右子树前序遍历起始：preL + lSize + 1（其中 lSize = mid - inL）
• 左子树中序遍历范围：[inL, mid - 1]
• 右子树中序遍历范围：[mid + 1, inR]

示例：

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

步骤1：根节点为3，在中序遍历中位置为1
步骤2：左子树中序遍历[9]，右子树中序遍历[15, 20, 7]
步骤3：递归构建左右子树
Copy

时间复杂度：O(n)
空间复杂度：O(n)

总结

通过前序遍历和中序遍历构建二叉树，关键点在于通过不断改变追踪索引，确定新子树的前序遍历和后序遍历的结果。

如果每一层都拿前一个子树的前序遍历结果，那么就无法确定新子树的根节点。

很容易错的地方在于正确处理了中序遍历的索引，但是没处理前序遍历的索引。理所当然认为不断shift preorder的头元素就是新子树的根。这是不对的。

左右子树的前序遍历节点范围是需要重新计算的。

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * val: number
 * left: TreeNode | null
 * right: TreeNode | null
 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 * }
 */

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const valToIdx = new Map<number, number>(inorder.map((v, i) => [v, i]));

  // 前序遍历序列的第一个节点是当前子树的根
  // 中序遍历序列可以根据这个节点划分成左右两部分，对应的就是当前子树的左右子树
  // 根据中序遍历划分子树节点个数
  // 当前操作：根据描述寻找当前子树的根
  // 下一个子问题：将preorder缩小为对应子树的preorder，inorder为对应子树的inorder

  function dfs(preL: number, inL: number, inR: number): TreeNode | null {
    if (preL >= preorder.length || inL > inR) {
      return null;
    }

    const val = preorder[preL];
    const mid = valToIdx.get(val)!;
    const lSize = mid - inL;

    const l = dfs(preL + 1, inL, mid - 1);
    const r = dfs(preL + lSize + 1, mid + 1, inR);

    return new TreeNode(val, l, r);
  }

  return dfs(0, 0, inorder.length - 1);
};
Copy