企业官网建设流程全解析

LeetCode 105 从先序与中序遍历构造二叉树：四种解法的完整指南（leetcode 仓库源码实战）

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文以 hints/binary-tree-from-preorder-and-inorder-traversal.md 的解题提示为主线，系统讲解「从先序遍历（preorder）与中序遍历（inorder）重建二叉树」这一经典问题：从数组切分直觉出发，逐步推导出哈希表优化、基于 limit 的 O(n) DFS，以及不依赖递归栈的 Morris 迭代构造，覆盖 O(n²) 到 O(n) 时间、O(1) 额外空间的完整优化链路。读完本文，你将掌握根节点定位、中序切分、全局索引 DFS 三种核心模式，并能直接对照本仓库 14 种语言的实现源码加深理解。

前置知识

在动手解决该问题前，建议先熟悉以下四块基础：

• 二叉树结构：理解节点通过 left / right 子指针相连的方式；
• 树的遍历顺序：先序遍历为「根 → 左 → 右」，中序遍历为「左 → 根 → 右」，两者的组合是本题唯一的信息来源；
• 递归 / DFS：通过把问题分解为左右子树的子问题来构造树；
• 哈希表：用字典把中序数组中「值 → 下标」的查找从 O(n) 降到 O(1)，这是把整体复杂度从 O(n²) 优化到 O(n) 的关键。

问题本质：两种遍历如何互补

题目要求：给定两个整数数组preorder与inorder，重建原始二叉树。例如：

preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7]

期望输出：[3, 9, 20, null, null, 15, 7]（层序表示）。

关键观察（即 hint 1 与 hint 2 的核心）：

• 先序遍历提供根节点：preorder的第一个元素永远是整棵树的根；
• 中序遍历提供子树划分：在inorder中，根节点左侧的所有元素属于左子树，右侧的所有元素属于右子树。因此中序数组被根节点「劈」成左右两半，且左右两半的元素个数（记为mid）恰好决定了先序数组中左右子树各占多少元素。

于是递归框架自然浮现：每次从preorder取出第一个值创建根节点，在中序数组中找到它的位置mid，左子树用preorder[1:mid+1]与inorder[0:mid]递归，右子树用preorder[mid+1:]与inorder[mid+1:]递归。hints 文档给出的推荐目标是O(n) 时间、O(n) 空间（n 为节点数），下文四种解法正是从朴素实现逐步逼近该目标的过程。

解法一：朴素的 DFS 数组切分（O(n²)）

思路与算法步骤

1. 若任一数组为空，返回null（递归基）；
2. 用preorder的第一个元素创建根节点；
3. 在inorder中线性查找根值的下标mid；
4. 用preorder[1:mid+1]与inorder[:mid]递归构建左子树；
5. 用preorder[mid+1:]与inorder[mid+1:]递归构建右子树；
6. 返回根节点。

这正是 hint 3 中提到的「线性查找会导致 O(n²) 解法」——每一层递归都要花费 O(n) 扫描中序数组寻找根的位置，而递归本身有 n 层。

# python/0105-construct-binary-tree-from-preorder-and-inorder-traversal.py class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: if not preorder or not inorder: return None root = TreeNode(preorder[0]) mid = inorder.index(preorder[0]) root.left = self.buildTree(preorder[1 : mid + 1], inorder[:mid]) root.right = self.buildTree(preorder[mid + 1 :], inorder[mid + 1 :]) return root

Java 版本使用Arrays.copyOfRange完成同样的切片（见 java/0105-construct-binary-tree-from-preorder-and-inorder-traversal.java），Go 版本则先封装index辅助函数线性定位再切片（见 go/0105-construct-binary-tree-from-preorder-and-inorder-traversal.go）。注意无论哪种语言，每次递归都创建了新的子数组，这也是空间开销的来源之一。

复杂度

• 时间复杂度：O(n²)（每层 O(n) 的线性查找 × n 层递归）；
• 空间复杂度：O(n)（递归栈深度）。

解法二：哈希表 + DFS（O(n) 时间）

hint 4 给出了关键优化方向：用哈希表把「任意节点在中序数组中的下标」查询降到 O(1)。同时避免创建新数组，改为用l、r两个索引标记当前子树在中序数组中的范围（hint 5）。

算法步骤

1. 建立哈希表，把inorder中每个值映射到它的下标；
2. 维护一个从 0 开始的全局先序索引pre_idx；
3. 定义递归函数dfs(l, r)，作用于中序数组区间[l, r]；
4. 若l > r，返回null（递归基）；
5. 取preorder[pre_idx]作为根值，随后pre_idx自增；
6. 用哈希表查出根值在中序数组中的位置mid；
7. 左子树递归dfs(l, mid-1)，右子树递归dfs(mid+1, r)；
8. 返回根节点。

class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: indices = {val: idx for idx, val in enumerate(inorder)} self.pre_idx = 0 def dfs(l, r): if l > r: return None root_val = preorder[self.pre_idx] self.pre_idx += 1 root = TreeNode(root_val) mid = indices[root_val] root.left = dfs(l, mid - 1) root.right = dfs(mid + 1, r) return root return dfs(0, len(inorder) - 1)

仓库中的 Java 实现（java/0105-construct-binary-tree-from-preorder-and-inorder-traversal.java）还展示了两种变体：第一种用HashMap<Integer, Integer> inorderPositions预存位置、用preorderIndex + (mid - inorderLow) + 1精确推导右子树先序起点；第二种即标准的全局pre_idx写法。C++ 实现（cpp/0105-construct-binary-tree-from-preorder-and-inorder-traversal.cpp）同样采用「引用传递的 index + i/j 区间」模式，与 hint 5 描述完全一致。

一个必须遵守的次序约定：先构建左子树，再构建右子树。因为先序遍历顺序是根 → 左 → 右，全局先序索引指向的下一个节点总是左子树中的节点；若先建右子树，会消费掉错误的先序节点，导致整棵树错乱（下文「常见陷阱」会再次强调）。

复杂度

• 时间复杂度：O(n)（每个节点恰好入树一次，哈希查询 O(1)）；
• 空间复杂度：O(n)（哈希表 + 递归栈）。

解法三：基于 limit 的最优 DFS（O(n)，免哈希表）

这一解法不再显式查找根的位置，而是利用中序数组的天然顺序：当某棵子树完成时，inorder[inIdx]恰好等于一个「边界值」。我们把这个边界值作为参数limit传入递归，遇到它即停止构建左子树并回溯。

算法步骤

1. 维护两个全局索引：preIdx（指向preorder）与inIdx（指向inorder）；
2. 定义递归函数dfs(limit)，构建子树直到遇到 limit 值；
3. 若preIdx >= n，返回null（节点已用完）；
4. 若inorder[inIdx] == limit，说明子树构建完毕，inIdx自增并返回null；
5. 用preorder[preIdx]创建根节点，preIdx自增；
6. 左子树用dfs(root.val)：因为中序中比根小的节点都排在根之前，遇到根值即停止；
7. 右子树沿用原始dfs(limit)；
8. 返回根节点，入口调用dfs(infinity)（或比任何节点值都大的值）。

class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: preIdx = inIdx = 0 def dfs(limit): nonlocal preIdx, inIdx if preIdx >= len(preorder): return None if inorder[inIdx] == limit: inIdx += 1 return None root = TreeNode(preorder[preIdx]) preIdx += 1 root.left = dfs(root.val) root.right = dfs(limit) return root return dfs(float('inf'))

各语言对「无穷大 limit」的处理值得对照学习：Python 用float('inf')，Java 用Integer.MAX_VALUE（java/0105-construct-binary-tree-from-preorder-and-inorder-traversal.java），C++ 用INT_MAX，JavaScript 用Infinity。仓库 javascript/0105-construct-binary-tree-from-preorder-and-inorder-traversal.js 还额外给出了以max = -Infinity为默认参数的函数式写法，思路一致但把索引封装进了indices对象。

复杂度

• 时间复杂度：O(n)；
• 空间复杂度：O(n)（递归栈）。

解法四：Morris 遍历（O(n) 时间，O(1) 额外空间）

如果连递归栈都想省掉，可以用 Morris 思路迭代构造：临时借用节点的 right 指针保存父节点引用，模拟调用栈，在建完左子树后清理这些临时指针并沿「栈」回溯。

算法步骤

1. 创建哑节点head，curr指向它；
2. 用索引i遍历preorder、j遍历inorder；
3. 为preorder[i]创建新节点，挂到curr的 right 子树上，curr移到新节点；
4. 当preorder[i]与inorder[j]不相等时，持续创建 left 子节点（并把父节点暂存进新节点的 right 指针）；
5. 一旦匹配，j自增；只要curr.right存在且值等于inorder[j]，就清除临时 right 链接并上移curr；
6. 循环直到所有节点处理完毕；
7. 返回head.right作为真正的根。

class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: head = TreeNode(None) curr = head i, j, n = 0, 0, len(preorder) while i < n and j < n: # Go right and then as far left as possible curr.right = TreeNode(preorder[i], right = curr.right) curr = curr.right i += 1 while i < n and curr.val != inorder[j]: curr.left = TreeNode(preorder[i], right=curr) curr = curr.left i += 1 j += 1 while curr.right and j < n and curr.right.val == inorder[j]: prev = curr.right curr.right = None curr = prev j += 1 return head.right

这段代码的关键在于「右指针当栈用」：TreeNode(preorder[i], right=curr)把当前节点作为父指针存进新节点的 right 域，最后一步再通过curr.right = None还原。Rust 版本（rust/0105-construct-binary-tree-from-preorder-and-inorder-traversal.rs）受Rc<RefCell<TreeNode>>所有权模型限制，需要显式borrow_mut()与clone()管理指针，是理解 Rust 树操作的良好范例。

复杂度

• 时间复杂度：O(n)；
• 空间复杂度：O(1) 额外空间（输出树本身仍占 O(n)）。

四种解法对比总览

hints 文档推荐的 O(n)/O(n) 目标对应解法二；若追求极致空间，解法四是面试加分项。

常见陷阱

陷阱一：切分数组时的越界（Off-by-One）

mid是根在中序数组中的下标，而左子树恰好有mid个元素，因此先序切分必须用preorder[1:mid+1]，而不是preorder[1:mid]：

# Wrong: preorder[1:mid] # Correct: preorder[1:mid+1]

陷阱二：先建右子树再建左子树

使用全局先序索引（解法二、三）时，必须先递归左子树。先序遍历的顺序是根 → 左 → 右，先建右子树会从preorder中消费掉本属于左子树的节点。

陷阱三：混淆先序与中序的角色

根节点永远来自preorder（第一个元素），而切分点要在inorder中查找。把两者对调会产生完全错误的树结构——这是 hint 1 反复强调「向先序数组要根、向中序数组要划分」的原因。

仓库源码与延伸阅读

• 完整题解文章：articles/binary-tree-from-preorder-and-inorder-traversal.md，包含全部 14 种语言的四种解法代码；
• 解题提示原文：hints/binary-tree-from-preorder-and-inorder-traversal.md；
• 单文件源码：Python（python/0105-construct-binary-tree-from-preorder-and-inorder-traversal.py）、TypeScript（typescript/0105-construct-binary-tree-from-preorder-and-inorder-traversal.ts）、C++（cpp/0105-construct-binary-tree-from-preorder-and-inorder-traversal.cpp）、Go（go/0105-construct-binary-tree-from-preorder-and-inorder-traversal.go）等，覆盖 C、C#、Dart、Java、JavaScript、Kotlin、Rust、Swift 等多个语言目录；
• 相关知识点可对照仓库中的 level-order-traversal-of-binary-tree.md、binary-tree-inorder-traversal.md、binary-tree-preorder-traversal.md 复习三种遍历，或参考 construct-binary-tree-from-inorder-and-postorder-traversal.md 迁移到中序 + 后序的变体。

建议的练习路径：先用解法一理解递归骨架，再按 hint 3 → hint 4 → hint 5 的顺序亲手把线性查找替换为哈希表查询，最后尝试在纸上模拟解法三的 limit 回溯过程——完成这三步后，Morris 版本也会变得水到渠成。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode