1. 题目解析与核心思路这道LeetCode hot100题目编号105要求根据二叉树的前序遍历和中序遍历序列重建原始二叉树。这是数据结构与算法中非常经典的递归应用问题也是大厂面试中的高频考点。前序遍历的顺序是根节点 → 左子树 → 右子树 中序遍历的顺序是左子树 → 根节点 → 右子树关键突破口在于前序遍历的第一个元素就是整棵树的根节点然后我们可以在中序遍历序列中找到这个根节点从而确定左右子树的范围。1.1 输入输出示例分析给定 前序遍历 preorder [3,9,20,15,7] 中序遍历 inorder [9,3,15,20,7]构建的二叉树应该是3 / \ 9 20 / \ 15 71.2 递归解法的时间复杂度最优解法的时间复杂度是O(n)因为我们需要遍历每个节点一次。空间复杂度也是O(n)主要用于存储哈希表和中序遍历的索引映射。2. 详细实现步骤与代码解析2.1 建立中序遍历索引映射首先我们需要建立一个哈希表来快速查找中序遍历中各个值的位置inorder_map {val:idx for idx, val in enumerate(inorder)}这个映射可以让我们在O(1)时间内找到任意值在中序遍历中的位置。2.2 递归函数设计递归函数需要以下参数pre_start: 前序遍历当前子树的起始索引in_start: 中序遍历当前子树的起始索引in_end: 中序遍历当前子树的结束索引def buildTree(preorder, inorder): inorder_map {val:idx for idx, val in enumerate(inorder)} pre_idx 0 def helper(in_start, in_end): nonlocal pre_idx if in_start in_end: return None root_val preorder[pre_idx] root TreeNode(root_val) pre_idx 1 in_index inorder_map[root_val] root.left helper(in_start, in_index - 1) root.right helper(in_index 1, in_end) return root return helper(0, len(inorder) - 1)2.3 递归过程详解每次递归先从前序遍历取当前根节点在中序遍历中找到该根节点的位置根据中序遍历结果划分左右子树递归构建左子树和右子树3. 迭代解法与优化思路3.1 使用栈的迭代解法def buildTree(preorder, inorder): if not preorder: return None root TreeNode(preorder[0]) stack [root] in_idx 0 for i in range(1, len(preorder)): node stack[-1] if node.val ! inorder[in_idx]: node.left TreeNode(preorder[i]) stack.append(node.left) else: while stack and stack[-1].val inorder[in_idx]: parent stack.pop() in_idx 1 parent.right TreeNode(preorder[i]) stack.append(parent.right) return root3.2 两种解法的比较递归解法更直观易懂但可能有栈溢出的风险迭代解法稍复杂但更节省空间。面试时建议先给出递归解法再讨论是否可以优化为迭代。4. 常见错误与调试技巧4.1 边界条件处理空输入检查单节点情况完全左斜树/右斜树4.2 索引越界问题特别注意递归终止条件if in_start in_end: return None4.3 测试用例设计建议测试以下情况普通二叉树只有左子树的树只有右子树的树单节点树空树5. 复杂度分析与优化空间5.1 时间复杂度优化使用哈希表存储中序遍历索引可以将查找操作从O(n)降到O(1)这是关键优化点。5.2 空间复杂度分析递归调用栈的空间复杂度是O(h)h是树的高度。最坏情况下斜树是O(n)平均是O(logn)。6. 相关题目拓展从中序和后序遍历构造二叉树LeetCode 106从前序和后序遍历构造二叉树LeetCode 889序列化和反序列化二叉树LeetCode 2977. 面试技巧与注意事项先理清思路再写代码画图辅助理解遍历序列的关系注意递归终止条件讨论输入验证和边界情况考虑是否可以优化为迭代解法在实际编码时建议先写出递归框架再填充细节。遇到问题时可以通过打印当前处理的子树范围来调试。