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:mid1]与inorder[0:mid]递归右子树用preorder[mid1:]与inorder[mid1:]递归。hints 文档给出的推荐目标是O(n) 时间、O(n) 空间n 为节点数下文四种解法正是从朴素实现逐步逼近该目标的过程。解法一朴素的 DFS 数组切分O(n²)思路与算法步骤若任一数组为空返回null递归基用preorder的第一个元素创建根节点在inorder中线性查找根值的下标mid用preorder[1:mid1]与inorder[:mid]递归构建左子树用preorder[mid1:]与inorder[mid1:]递归构建右子树返回根节点。这正是 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 rootJava 版本使用Arrays.copyOfRange完成同样的切片见 java/0105-construct-binary-tree-from-preorder-and-inorder-traversal.javaGo 版本则先封装index辅助函数线性定位再切片见 go/0105-construct-binary-tree-from-preorder-and-inorder-traversal.go。注意无论哪种语言每次递归都创建了新的子数组这也是空间开销的来源之一。复杂度时间复杂度O(n²)每层 O(n) 的线性查找 × n 层递归空间复杂度O(n)递归栈深度。解法二哈希表 DFSO(n) 时间hint 4 给出了关键优化方向用哈希表把「任意节点在中序数组中的下标」查询降到 O(1)。同时避免创建新数组改为用l、r两个索引标记当前子树在中序数组中的范围hint 5。算法步骤建立哈希表把inorder中每个值映射到它的下标维护一个从 0 开始的全局先序索引pre_idx定义递归函数dfs(l, r)作用于中序数组区间[l, r]若l r返回null递归基取preorder[pre_idx]作为根值随后pre_idx自增用哈希表查出根值在中序数组中的位置mid左子树递归dfs(l, mid-1)右子树递归dfs(mid1, r)返回根节点。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还展示了两种变体第一种用HashMapInteger, 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 的最优 DFSO(n)免哈希表这一解法不再显式查找根的位置而是利用中序数组的天然顺序当某棵子树完成时inorder[inIdx]恰好等于一个「边界值」。我们把这个边界值作为参数limit传入递归遇到它即停止构建左子树并回溯。算法步骤维护两个全局索引preIdx指向preorder与inIdx指向inorder定义递归函数dfs(limit)构建子树直到遇到 limit 值若preIdx n返回null节点已用完若inorder[inIdx] limit说明子树构建完毕inIdx自增并返回null用preorder[preIdx]创建根节点preIdx自增左子树用dfs(root.val)因为中序中比根小的节点都排在根之前遇到根值即停止右子树沿用原始dfs(limit)返回根节点入口调用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_VALUEjava/0105-construct-binary-tree-from-preorder-and-inorder-traversal.javaC 用INT_MAXJavaScript 用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 指针保存父节点引用模拟调用栈在建完左子树后清理这些临时指针并沿「栈」回溯。算法步骤创建哑节点headcurr指向它用索引i遍历preorder、j遍历inorder为preorder[i]创建新节点挂到curr的 right 子树上curr移到新节点当preorder[i]与inorder[j]不相等时持续创建 left 子节点并把父节点暂存进新节点的 right 指针一旦匹配j自增只要curr.right存在且值等于inorder[j]就清除临时 right 链接并上移curr循环直到所有节点处理完毕返回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], rightcurr) 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], rightcurr)把当前节点作为父指针存进新节点的 right 域最后一步再通过curr.right None还原。Rust 版本rust/0105-construct-binary-tree-from-preorder-and-inorder-traversal.rs受RcRefCellTreeNode所有权模型限制需要显式borrow_mut()与clone()管理指针是理解 Rust 树操作的良好范例。复杂度时间复杂度O(n)空间复杂度O(1) 额外空间输出树本身仍占 O(n)。四种解法对比总览解法核心思想时间空间额外是否依赖哈希表是否递归朴素 DFS 切分线性查找根 数组切片O(n²)O(n)否是哈希表 DFS值→下标映射 区间索引O(n)O(n)是是limit DFS中序遇界即回溯O(n)O(n)否是Morris 遍历右指针模拟调用栈O(n)O(1)否否hints 文档推荐的 O(n)/O(n) 目标对应解法二若追求极致空间解法四是面试加分项。常见陷阱陷阱一切分数组时的越界Off-by-Onemid是根在中序数组中的下标而左子树恰好有mid个元素因此先序切分必须用preorder[1:mid1]而不是preorder[1:mid]# Wrong: preorder[1:mid] # Correct: preorder[1:mid1]陷阱二先建右子树再建左子树使用全局先序索引解法二、三时必须先递归左子树。先序遍历的顺序是根 → 左 → 右先建右子树会从preorder中消费掉本属于左子树的节点。陷阱三混淆先序与中序的角色根节点永远来自preorder第一个元素而切分点要在inorder中查找。把两者对调会产生完全错误的树结构——这是 hint 1 反复强调「向先序数组要根、向中序数组要划分」的原因。仓库源码与延伸阅读完整题解文章articles/binary-tree-from-preorder-and-inorder-traversal.md包含全部 14 种语言的四种解法代码解题提示原文hints/binary-tree-from-preorder-and-inorder-traversal.md单文件源码Pythonpython/0105-construct-binary-tree-from-preorder-and-inorder-traversal.py、TypeScripttypescript/0105-construct-binary-tree-from-preorder-and-inorder-traversal.ts、Ccpp/0105-construct-binary-tree-from-preorder-and-inorder-traversal.cpp、Gogo/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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考