从前序与中序遍历序列构造二叉树（LeetCode 105）
题目链接：从前序与中序遍历序列构造二叉树（LeetCode 105）
难度：中等
1. 题目描述
给定两个整数数组preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
要求：
- 树中不存在重复元素
- 数组长度 1 <= n <= 3000
- -3000 <= preorder[i], inorder[i] <= 3000
示例：
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]输入: preorder = [-1], inorder = [-1] 输出: [-1]2. 问题分析
2.1 规律
- 先序遍历：根节点 -> 左子树 -> 右子树
- 中序遍历：左子树 -> 根节点 -> 右子树
- 先序的第一个元素总是根节点，在中序中找到根节点的位置，可以分割左/右子树。
- 递归构建：左子树的前序/中序子序列，右子树的前序/中序子序列。
- 核心问题：如何高效找到中序中根节点的位置，以分割子树？
2.2 贪心思路
我们使用递归 + 哈希表优化：
- 使用哈希表存储中序遍历的值到索引的映射，便于 O(1) 查找根节点位置。
- 递归函数：参数为前序/中序的起始/结束索引。
- 步骤：
- 如果子树为空（start > end），返回 None。
- 取前序第一个元素作为根，pre_idx += 1。
- 在中序中找到根索引 root_in_idx。
- 递归构建左子树：中序 [in_start, root_in_idx-1]，前序相应部分。
- 递归构建右子树：中序 [root_in_idx+1, in_end]，前序相应部分。
- 全局 pre_idx 跟踪前序位置，避免切片开销。
3. 代码实现
Python
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defbuildTree(self,preorder:List[int],inorder:List[int])->Optional[TreeNode]:defhelper(in_start,in_end):nonlocalpre_idxifin_start>in_end:returnNoneroot_val=preorder[pre_idx]root=TreeNode(root_val)pre_idx+=1root_in_idx=idx_map[root_val]root.left=helper(in_start,root_in_idx-1)root.right=helper(root_in_idx+1,in_end)returnroot n=len(preorder)idx_map={val:ifori,valinenumerate(inorder)}pre_idx=0returnhelper(0,n-1)C++
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public:TreeNode*buildTree(vector<int>&preorder,vector<int>&inorder){unordered_map<int,int>idx_map;for(inti=0;i<inorder.size();++i){idx_map[inorder[i]]=i;}intpre_idx=0;returnhelper(preorder,inorder,idx_map,pre_idx,0,inorder.size()-1);}private:TreeNode*helper(vector<int>&preorder,vector<int>&inorder,unordered_map<int,int>&idx_map,int&pre_idx,intin_start,intin_end){if(in_start>in_end){returnnullptr;}introot_val=preorder[pre_idx];TreeNode*root=newTreeNode(root_val);++pre_idx;introot_in_idx=idx_map[root_val];root->left=helper(preorder,inorder,idx_map,pre_idx,in_start,root_in_idx-1);root->right=helper(preorder,inorder,idx_map,pre_idx,root_in_idx+1,in_end);returnroot;}};4. 复杂度分析
- 时间复杂度：O(n)，哈希表构建 O(n)，递归遍历每个节点一次
- 空间复杂度：O(n)，哈希表 O(n)，递归栈最坏 O(n)
5. 总结
- 树重建问题+遍历序列→ 递归分割是首选
- 核心使用哈希表优化索引查找，很通用
- 类似 BFS 的序列化，但这里是反序列化
- 可扩展到后序 + 中序的变体
复习
面试经典150题[012]：O(1) 时间插入、删除和获取随机元素（LeetCode 380）
面试经典150题[042]：有效的字母异位词（LeetCode 242）
面试经典150题[057]：链表中是否有环（LeetCode 141）
