从前序与中序遍历序列构造二叉树
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
题目保证 preorder 与 inorder 元素无重复，且确实对应一棵二叉树的前序与中序序列；长度相等且在 [1, 3000] 内。
示例 1
示例 2
模拟答题者思考
1. 暴力直觉：枚举所有二叉树形状，对每个树检查先序、中序是否匹配——指数级，不可行。
2. 先序的第一个数一定是当前子树的根；中序里根左边的连续段是左子树的中序，右边是右子树的中序——子问题与整题同型，天然分治。
3. 若每次在中序里线性找根位置并切片 preorder/inorder，最坏 O(n²)；用哈希表记下每个值在中序的下标，配合全局 pre_i 按先序依次「消费」节点，每个值只处理一次 → O(n)。
4. 示例 1：根 3，中序 mid=1，左区间 [0,0] 得到节点 9，右区间 [2,4] 先建 20 再 15、7，与先序 [20,15,7] 一致。
5. 递归深度 O(h)，表 O(n)；必须先递归左子树再右子树，否则 pre_i 与先序不对齐。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
preorder[pre_i] | int / 游标 | 定义：全局先序指针，下一个要「落地」为树节点的值 维护：每创建一个节点后 pre_i += 1，顺序与先序遍历一致更新：递归先建左再建右，指针自然扫完整棵树的先序 |
in_left, in_right | int | 定义：当前子树在 inorder 中的闭区间下标维护： in_left > in_right 表示空子树，返回 null更新：根在中序位置 mid 处，左子树 [in_left, mid-1]，右子树 [mid+1, in_right] |
idx_map[val] | 哈希表 | 定义：中序每个值 → 下标，O(1) 找根在中序中的位置 维护：构造前一次性建好，全程不变 更新：读到根值 root_val 后 mid = idx_map[root_val] 用于切分左右区间 |
root | TreeNode* | 定义：当前子树的根，值来自当前 preorder[pre_i]维护：先挂好 left、right 再返回给上层更新： root.left = dfs(...) 再 root.right = dfs(...)（顺序必须与先序一致） |
落码步骤
1. 建 idx_map：inorder[i] → i
2. 定义 dfs(in_left, in_right)：若 in_left > in_right 返回 null
3. 取 root_val = preorder[pre_i++]，mid = idx_map[root_val]，新建根节点
4. root.left = dfs(in_left, mid - 1)，再 root.right = dfs(mid + 1, in_right)
5. 从 dfs(0, len(inorder)-1) 返回整棵树的根
代码实现
class Solution:
def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
idx_map = {v: i for i, v in enumerate(inorder)}
pre_i = 0
def dfs(in_left: int, in_right: int) -> TreeNode | None:
nonlocal pre_i
if in_left > in_right:
return None
root_val = preorder[pre_i]
pre_i += 1
mid = idx_map[root_val]
node = TreeNode(root_val)
node.left = dfs(in_left, mid - 1)
node.right = dfs(mid + 1, in_right)
return node
return dfs(0, len(inorder) - 1)class Solution {
int pre_i = 0;
unordered_map<int, int> idx_map;
TreeNode* dfs(int in_left, int in_right, vector<int>& preorder) {
if (in_left > in_right) return nullptr;
int root_val = preorder[pre_i++];
int mid = idx_map[root_val];
auto* root = new TreeNode(root_val);
root->left = dfs(in_left, mid - 1, preorder);
root->right = dfs(mid + 1, in_right, preorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
pre_i = 0;
idx_map.clear();
for (int i = 0; i < (int)inorder.size(); ++i)
idx_map[inorder[i]] = i;
return dfs(0, (int)inorder.size() - 1, preorder);
}
};
// 时间 O(n)，空间 O(n)复杂度分析
O(n)
O(n)（中序下标哈希表 + 递归栈 O(h)）
常见坑
先递归右子树再左子树：pre_i 按先序推进，顺序错了会挂错节点。
右子树中序区间写成 [mid, in_right]：根已在 mid，右子树必须从 mid + 1 开始。
用切片复制子数组：正确但 Python 切片会多 O(n²) 拷贝；应像上面用下标区间 + 全局先序指针。
必测边界 Case
preorder = [-1], inorder = [-1] → 根 -1，无孩子
pre = [1,2,3], in = [3,2,1] → 1 的左子树为空、右子树为 2→3
pre = [1,2,3], in = [1,2,3] → 每层只有右孩子
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
根在中序最左端 → dfs(in_left, mid-1) 立即返回 null