Construct Binary Tree from Preorder and Inorder Traversal（从前序与中序遍历序列构造二叉树）

题目 / Problem

中文： 给定两个整数数组 preorder 和 inorder，其中 preorder 是一棵二叉树的前序遍历结果，inorder 是同一棵树的中序遍历结果。构造并返回这棵二叉树。

数组中的所有节点值互不相同，并且两个数组包含相同的节点值。

English: Given two integer arrays preorder and inorder, where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

All node values are unique, and both arrays contain the same values.

示例 / Examples

Example 1

Input:
preorder = [3,9,20,15,7]
inorder  = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7]

构造出的二叉树为：
The constructed tree is:

由前序和中序遍历构造出的二叉树 / Binary tree constructed from preorder and inorder traversals

Example 2

Input:  preorder = [-1], inorder = [-1]
Output: [-1]

只有一个节点时，该节点就是根节点。
With one node, that node is the root.

约束 / Constraints

1 <= preorder.length <= 3000
inorder.length === preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 中的值互不相同。
Values in preorder and inorder are unique.
inorder 中的每个值也存在于 preorder 中。
Every value in inorder also appears in preorder.
两个数组保证分别是同一棵二叉树的前序和中序遍历结果。
Both arrays are guaranteed to be valid traversals of the same binary tree.

前序与中序遍历的性质 / Traversal Properties

前序遍历 / Preorder

根节点 → 左子树 → 右子树
Root → Left subtree → Right subtree

因此，当前尚未使用的第一个前序遍历元素一定是当前子树的根节点。
Therefore, the first unused preorder value is always the root of the current subtree.

中序遍历 / Inorder

左子树 → 根节点 → 右子树
Left subtree → Root → Right subtree

在中序数组中找到根节点后，它会把当前区间分成左右两部分：
After locating the root in the inorder array, it splits the current range into two parts:

[左子树节点] 根节点 [右子树节点]
[left subtree] root [right subtree]

解题思路：递归分治 / Approach: Recursive Divide and Conquer

使用 preorderIndex 指向前序数组中下一个尚未使用的根节点。递归函数 build(left, right) 负责构造中序数组闭区间 [left, right] 对应的子树。
Use preorderIndex to point to the next unused root in preorder. The recursive function build(left, right) constructs the subtree corresponding to the closed inorder range [left, right].

每次递归执行以下步骤：
Each recursive call performs these steps:

如果 left > right，当前区间为空，返回 null。
If left > right, the range is empty, so return null.
读取 preorder[preorderIndex] 作为根节点，并移动 preorderIndex。
Read preorder[preorderIndex] as the root and advance preorderIndex.
在中序数组中找到根节点的位置 rootIndex。
Locate the root's position rootIndex in inorder.
递归构造中序区间 [left, rootIndex - 1] 对应的左子树。
Recursively construct the left subtree from [left, rootIndex - 1].
递归构造中序区间 [rootIndex + 1, right] 对应的右子树。
Recursively construct the right subtree from [rootIndex + 1, right].

必须先构造左子树，再构造右子树，因为前序遍历中的顺序是“根 → 左 → 右”。
The left subtree must be built before the right subtree because preorder follows root-left-right order.

哈希表优化 / Hash Map Optimization

如果每次都使用 inorder.indexOf(rootValue) 查找根节点，最坏情况下每层都需要线性扫描，时间复杂度会达到 O(n²)。
Calling inorder.indexOf(rootValue) during every recursive step may scan linearly at every level, producing O(n²) time in the worst case.

预先建立“节点值 → 中序下标”的映射：
Precompute a value-to-inorder-index map:

const inorderIndex = new Map();

for (let i = 0; i < inorder.length; i++) {
  inorderIndex.set(inorder[i], i);
}

由于节点值互不相同，每个值都能唯一对应一个中序下标，之后查找只需 O(1) 时间。
Because node values are unique, every value maps to exactly one inorder index, making each lookup O(1).

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *   this.val = val ?? 0;
 *   this.left = left ?? null;
 *   this.right = right ?? null;
 * }
 */

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
function buildTree(preorder, inorder) {
  const inorderIndex = new Map();

  for (let i = 0; i < inorder.length; i++) {
    inorderIndex.set(inorder[i], i);
  }

  let preorderIndex = 0;

  function build(left, right) {
    if (left > right) {
      return null;
    }

    const rootValue = preorder[preorderIndex];
    preorderIndex++;

    const root = new TreeNode(rootValue);
    const rootIndex = inorderIndex.get(rootValue);

    root.left = build(left, rootIndex - 1);
    root.right = build(rootIndex + 1, right);

    return root;
  }

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

执行过程 / Walkthrough

使用 Example 1：
Using Example 1:

preorder = [3,9,20,15,7]
inorder  = [9,3,15,20,7]

第一步：根节点 `3` / Step 1: Root `3`

前序数组的第一个值是 3，因此根节点为 3。
The first preorder value is 3, so 3 is the root.

inorder = [9] 3 [15,20,7]
           ↑       ↑
       左子树     右子树
       left       right

第二步：构造左子树 / Step 2: Build the Left Subtree

前序中的下一个值是 9。中序左区间只有 [9]，所以 9 是叶子节点。
The next preorder value is 9. The left inorder range contains only [9], so 9 is a leaf.

第三步：构造右子树 / Step 3: Build the Right Subtree

前序中的下一个值是 20，它是右子树的根：
The next preorder value is 20, making it the right-subtree root:

右子树 inorder / Right-subtree inorder:
[15] 20 [7]
  ↑       ↑
 left    right

继续构造得到左子节点 15 和右子节点 7。
Continuing recursively produces left child 15 and right child 7.

最终结果：
Final result:

递归区间变化 / Recursive Ranges

根节点 / Root	中序区间 / Inorder range	左区间 / Left range	右区间 / Right range
`3`	`[0,4]`	`[0,0]`	`[2,4]`
`9`	`[0,0]`	空 / Empty	空 / Empty
`20`	`[2,4]`	`[2,2]`	`[4,4]`
`15`	`[2,2]`	空 / Empty	空 / Empty
`7`	`[4,4]`	空 / Empty	空 / Empty

为什么节点值必须唯一？ / Why Must Values Be Unique?

构造过程中需要通过根节点值确定它在中序数组中的唯一位置。如果值重复，一个值可能对应多个位置，仅凭前序和中序数组就无法使用当前方法唯一确定分割点。
Construction requires locating the root's unique position in inorder. With duplicate values, one value could map to multiple indices, so this method could not determine the split point unambiguously from the traversals alone.

本题保证所有值互不相同，因此哈希表映射是明确的。
The problem guarantees unique values, so the hash-map lookup is unambiguous.

复杂度 / Complexity

设节点数量为 n，树高为 h。
Let n be the number of nodes and h the tree height.

时间复杂度 / Time: O(n)，每个节点创建一次，每个中序下标查询为 O(1)。
Every node is created once, and each inorder-index lookup takes O(1).
空间复杂度 / Space: O(n)，哈希表需要 O(n)，递归栈需要 O(h)。
The map uses O(n) space, and the recursion stack uses O(h).

平衡树的递归深度为 O(log n)；完全偏斜的树可能达到 O(n)。
A balanced tree has recursion depth O(log n), while a completely skewed tree may reach O(n).

易错点 / Common Pitfalls

前序遍历用于依次确定根节点，中序遍历用于划分左右子树。
Use preorder to choose roots and inorder to split left and right subtrees.
必须先递归构造左子树，再构造右子树。
Build the left subtree before the right subtree.
空区间的判断条件是 left > right，此时返回 null。
An empty range satisfies left > right, at which point return null.
中序区间使用闭区间，因此左子树是 [left, rootIndex - 1]，右子树是 [rootIndex + 1, right]。
With closed inorder ranges, the left subtree is [left, rootIndex - 1] and the right subtree is [rootIndex + 1, right].
不要在每次递归中切割新数组，否则会增加时间和空间开销。
Avoid slicing new arrays during recursion, which adds time and space overhead.
当树高度接近 3000 时，某些 JavaScript 运行环境可能接近递归调用栈限制。
When tree height approaches 3000, some JavaScript runtimes may approach their recursion-stack limit.

Construct Binary Tree from Preorder and Inorder Traversal