LeetCode 105中等二叉树 · 构造
从前序与中序遍历序列构造二叉树 图解题解
前序第一个值是根，中序根的位置决定左右子树大小——两者缺一就没法唯一还原。
前序告诉你「谁是当前这棵树的根」，中序告诉你「根的左边有几个节点、右边有几个」。两个序列配合：从前序取出根，再去中序里找到根的位置，左侧划给左子树、右侧划给右子树；然后对两段各自递归重复这个过程，直到划出来的区间为空。
这道题到底在问什么
给定 preorder 和 inorder，构造原二叉树。
- preorder
- [3,9,20,15,7]
- inorder
- [9,3,15,20,7]
- 输出
- 构造出的二叉树
最优解：一步一步想明白
- 3递归时只传左右边界，避免反复切片。
- 4根 = 3前序顺序是 根 → 左 → 右。
- 5左 [9] 右 [15,20,7]中序顺序是 左 → 根 → 右。
- 6前序下一个 9左子树只有一个节点，直接完成。
- 7preorder[2]=20递归处理右边界。
- 8左 15 右 7所以 15 是 20 的左子树，7 是右子树。
- 9叶子节点到叶子时递归边界会返回。
- 10叶子节点左右子树都建完，回到 20。
- 113 的左 9，右 20整棵树构造完成。
- 12不要每次切片用 preorder 指针和 inorder 左右边界即可。
- 15构造树题最重要的是边界和指针不要乱。
- 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：递归里反复 preorder.pop(0)
✓ 对：用 pre_i 指针前进
pop(0) 是 O(n)，会拖慢整体复杂度
✗ 错：左右边界写错
✓ 对：左 [l,mid-1]，右 [mid+1,r]
mid 是根，不能再放进子树
完整代码（Python / C++ / Java）
Python
class Solution:
def buildTree(self, preorder, inorder):
pos = {v: i for i, v in enumerate(inorder)}
pre_i = 0
def build(l, r):
nonlocal pre_i
if l > r:
return None
root_val = preorder[pre_i]
pre_i += 1
root = TreeNode(root_val)
mid = pos[root_val]
root.left = build(l, mid - 1)
root.right = build(mid + 1, r)
return root
return build(0, len(inorder) - 1)C++
class Solution {
vector<int> pre; unordered_map<int,int> pos; int preIdx = 0;
TreeNode* build(int l, int r) {
if (l > r) return nullptr;
int val = pre[preIdx++];
TreeNode* root = new TreeNode(val); int mid = pos[val];
root->left = build(l, mid - 1);
root->right = build(mid + 1, r);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
pre = preorder;
for (int i = 0; i < inorder.size(); i++) pos[inorder[i]] = i;
return build(0, inorder.size() - 1);
}
};Java
class Solution {
int[] pre; Map<Integer,Integer> pos = new HashMap<>(); int preIdx = 0;
TreeNode build(int l, int r) {
if (l > r) return null;
int val = pre[preIdx++];
TreeNode root = new TreeNode(val); int mid = pos.get(val);
root.left = build(l, mid - 1);
root.right = build(mid + 1, r);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
pre = preorder;
for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
return build(0, inorder.length - 1);
}
}套路模板 · 前序中序构造树
class Solution:
def buildTree(self, preorder, inorder):
pos = {v: i for i, v in enumerate(inorder)}
idx = 0
def build(l, r):
nonlocal idx
if l > r:
return None
val = preorder[idx]
idx += 1
root = TreeNode(val)
mid = pos[val]
root.left = build(l, mid - 1)
root.right = build(mid + 1, r)
return root
return build(0, len(inorder) - 1)class Solution {
vector<int> pre; unordered_map<int,int> pos; int preIdx = 0;
TreeNode* build(int l, int r) {
if (l > r) return nullptr;
int val = pre[preIdx++];
TreeNode* root = new TreeNode(val); int mid = pos[val];
root->left = build(l, mid - 1);
root->right = build(mid + 1, r);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
pre = preorder;
for (int i = 0; i < inorder.size(); i++) pos[inorder[i]] = i;
return build(0, inorder.size() - 1);
}
};class Solution {
int[] pre; Map<Integer,Integer> pos = new HashMap<>(); int preIdx = 0;
TreeNode build(int l, int r) {
if (l > r) return null;
int val = pre[preIdx++];
TreeNode root = new TreeNode(val); int mid = pos.get(val);
root.left = build(l, mid - 1);
root.right = build(mid + 1, r);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
pre = preorder;
for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
return build(0, inorder.length - 1);
}
}复杂度
时间复杂度
O(n)
每个节点建一次，哈希定位 O(1)
空间复杂度
O(n)
pos 表和递归栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 从前序与中序遍历序列构造二叉树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么必须「前序+中序」(或后序+中序)才能唯一确定树？+
前序/后序定「谁是根」，中序定「根的左右各有哪些节点」。光有前序无法知道左右子树的分界；只有前序+后序也无法唯一(缺中序定界)。
怎么加速在中序里找根？+
用哈希表预存 中序值→下标，O(1) 定位根，避免每次线性扫描；整体从 O(n²) 降到 O(n)。
递归的出口是什么？+
当前区间为空(left 大于 right)时返回 null，这就是递归的底。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。