前序首元素是根，用哈希表定位中序分界，递归构造区间。
OJ: leetcodecn
题目 ID: construct-binary-tree-from-preorder-and-inorder-traversal
难度:普及+/提高
标签:二叉树递归哈希表cpppython
日期: 2026-07-29 13:10
题意
根据前序和中序遍历结果构造二叉树。
思路
前序第一个为根，在中序中根左侧为左子树、右侧为右子树。哈希表加速定位。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode *buildTree(vector<int> &pre, vector<int> &in) {
unordered_map<int, int> pos;
for (int i = 0; i < (int)in.size(); i++)
pos[in[i]] = i;
int idx = 0;
// 中序区间 [l, r] 决定子树范围，前序指针依次给出每棵子树的根。
function<TreeNode *(int, int)> build = [&](int l, int r) -> TreeNode * {
if (l > r)
return nullptr;
int v = pre[idx++];
int m = pos[v];
TreeNode *root = new TreeNode(v);
root->left = build(l, m - 1);
root->right = build(m + 1, r);
return root;
};
return build(0, in.size() - 1);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> pre(n), in(n);
for (int &x : pre)
cin >> x;
for (int &x : in)
cin >> x;
auto r = Solution().buildTree(pre, in);
// 输出层序验证
queue<TreeNode *> q;
q.push(r);
while (!q.empty()) {
auto cur = q.front();
q.pop();
if (!cur) {
cout << "-1 ";
continue;
}
cout << cur->val << ' ';
q.push(cur->left);
q.push(cur->right);
}
return 0;
}python
#!/usr/bin/env python3
from collections import deque
from typing import List, Optional
class TreeNode:
def __init__(self, x):
self.val = x
self.left = self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
pos = {v: i for i, v in enumerate(inorder)}
idx = 0
def build(l, r):
nonlocal idx
if l > r:
return None
v = preorder[idx]
idx += 1
m = pos[v]
root = TreeNode(v)
root.left = build(l, m - 1)
root.right = build(m + 1, r)
return root
return build(0, len(inorder) - 1)
def main():
n = int(input())
pre = list(map(int, input().split()))
ino = list(map(int, input().split()))
r = Solution().buildTree(pre, ino)
q = deque([r])
while q:
cur = q.popleft()
if not cur:
print("-1", end=" ")
continue
print(cur.val, end=" ")
q.append(cur.left)
q.append(cur.right)
if __name__ == "__main__":
main()复杂度
时间 O(n)，空间 O(n)。
总结
前序定根、中序分左右是二叉树递归构造的基本模型。