105. 从前序与中序遍历序列构造二叉树
4 min
题目
解法：递归分治
思路
核心思想是利用前序遍历首元素为根节点、中序遍历以根节点分左右子树的性质，递归构建整棵树。
该方法正确是因为前序遍历的第一个节点必为根节点，在中序遍历中找到该根节点后，其左侧所有节点构成左子树，右侧构成右子树。由于树中无重复元素，哈希表可准确定位根节点位置，且左右子树节点数量一致，因此可在前序遍历中精确划分左右子树区间，递归过程不会遗漏或错配任何节点。
- Step 1: 建立中序遍历值到索引的哈希映射，实现 O(1) 查找根节点位置
- Step 2: 递归函数接收前序和中序的左右边界，若左边界超过右边界则返回空指针
- Step 3: 取前序遍历第一个元素作为根节点值，创建根节点
- Step 4: 在哈希映射中查找根节点在中序遍历中的位置 k
- Step 5: 计算左子树大小 leftSize = k - inL
- Step 6: 递归构建左子树，前序区间为 [preL+1, preL+leftSize]，中序区间为 [inL, k-1]
- Step 7: 递归构建右子树，前序区间为 [preL+leftSize+1, preR]，中序区间为 [k+1, inR]
- Step 8: 返回根节点
复杂度
- 时间复杂度: ，其中 n 为节点数。每个节点仅被访问一次，哈希查找耗时 O(1)。
- 空间复杂度: ，用于存储哈希表和递归调用栈。
代码
class Solution {
public:
unordered_map<int,int> pos;
TreeNode* build(vector<int>& preorder, int preL, int preR,
int inL, int inR) {
if(preL > preR) return nullptr;
int rootVal = preorder[preL];
TreeNode* root = new TreeNode(rootVal);
int k = pos[rootVal];
int leftSize = k - inL;
root->left = build(preorder,
preL+1,
preL+leftSize,
inL,
k-1);
root->right = build(preorder,
preL+leftSize+1,
preR,
class Solution {
public:
unordered_map<int,int> pos;
TreeNode* build(vector<int>& preorder, int preL, int preR,
int inL, int inR) {
if(preL > preR) return nullptr;
int rootVal = preorder[preL];
TreeNode* root = new TreeNode(rootVal);
int k = pos[rootVal];
int leftSize = k - inL;
root->left = build(preorder,
preL+1,
preL+leftSize,
inL,
k-1);
root->right = build(preorder,
preL+leftSize+1,
preR,
k+1,
inR);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i=0;i<inorder.size();i++)
pos[inorder[i]] = i;
return build(preorder,0,preorder.size()-1,0,inorder.size()-1);
}
};