1. 从一道经典面试题说起为什么LeetCode105值得单独写一篇如果只是想在 LeetCode 上刷过105 这道题半小时就能背下一套递归模板拿前序第一个元素当根去中序里找位置切开左右区间递归。但刷过和真正理解中间隔着一条很宽的沟。我面试过不少候选人也帮朋友做过 mock interview一个很明显的分界线就在这里——能把 105 讲清楚的人二叉树相关的题目基本都拦不住他只会背模板的人换到 106中序后序或者 889前序后序就立刻卡壳。那道题的价值不仅仅在于从前序与中序遍历序列构造二叉树这个算法本身而在于它是理解遍历序列如何携带树结构信息的最佳入门样本。树的结构是二维的而遍历序列是一维的一道题教会你如何在这两种形态之间做双向映射。这个能力往小里说是刷题必备往大里说序列化反序列化、AST 解析、数据库索引重建背后全是同一套思维。这篇文章我会按我自己的学习路径来组织先讲清楚前序和中序为什么能唯一确定一棵二叉树再给出手写递归实现然后逐步深入到哈希优化和迭代构造这两种进阶写法最后专门用一节聊聊面试官真正想考察的点以及这类题的工程联想。无论你是刚开始刷二叉树的新手还是准备冲刺大厂面试的候选人应该都能从里面找到自己需要的那层内容。多说一句网上这道题的题解非常多但我发现大部分都是在给结论很少有文章把索引偏移的推导过程、边界条件的取舍逻辑、以及运行时错误的完整排查链路讲透。这些恰恰是最容易让新手卡壳的地方也是本文想重点补上的部分。1.1 这道题在面试中的生态位LeetCode 105 是二叉树的遍历类题目里非常特殊的一道。它不像二叉树的最大深度那样只要会递归模板就能写也不像层序遍历那样有明确的数据结构套路。它的核心是序列解析给你两条一维序列要还原出二维的树形结构。这个能力在面试中几乎是被默认考察的。比如很多公司喜欢在系统设计或项目深挖环节问如何序列化一棵二叉树如何从文件恢复出一颗语法树本质上都是这道题的变体。如果你能把 105 的索引映射逻辑理解到闭着眼也能写对边界的程度这类问题基本就是白送分。1.2 题面回顾与输入前置条件题目本身很简洁给定两个整数数组preorder和inorder分别代表一棵二叉树的前序遍历和中序遍历结果请你构造并返回这棵二叉树的根节点。需要特别强调一个隐式前置条件树中的节点值互不相同。这是整道题能成立的根本前提。因为中序序列的作用是定位根节点把左右子树分在了哪里如果存在重复值这个定位就存在歧义无法唯一确定树的结构。LeetCode 105 的题目描述里保证了无重复元素面试时如果遇到变体题这个条件需要先确认。还有一点值得注意输入保证两个序列来自同一棵二叉树因此不需要额外校验合法性。但在实际工程里如果你拿到的两条序列不可信就需要在构造过程中加入校验逻辑——这个延伸我们放到后面讲错误排查时再说。2. 递归构建的核心逻辑前序和中序到底怎么配合很多人会背前序找根中序分左右这句话但真要问他为什么中序能确定左右子树的大小却说不清楚。把这一步想透了后续所有代码都是顺理成章的。2.1 前序序列的关键信息谁是根前序遍历的顺序是根节点 - 左子树 - 右子树。这意味着在一棵子树对应的前序区间里第一个元素就是这棵子树的根节点。这个信息是递归构造的启动点。举个例子preorder [3, 9, 20, 15, 7]那么整棵树的根必然是 3。这一步没有任何悬念。但光有前序还不够——前序只告诉我们根是谁却无法告诉我们哪些节点属于左子树哪些属于右子树。如果只用前序序列你能构造出无数种形态不同的二叉树。2.2 中序序列的关键信息左右子树的切分线中序遍历的顺序是左子树 - 根节点 - 右子树。中序序列的妙处在于一旦知道了根节点的值你就可以在序列中精确地找到根的位置它左边的所有元素都属于左子树右边的所有元素都属于右子树。还是用上面的例子inorder [9, 3, 15, 20, 7]根是 3在数组中下标为 1。那么[9]就是左子树的中序序列[15, 20, 7]就是右子树的中序序列。到这里就出现了一个关键问题左右子树的大小确定了但前序序列中左右子树各占多少个节点这正是从理解原理到写出代码之间最关键的一步。2.3 尺寸联动两个序列之间的桥梁中序序列已经告诉我们左子树有 1 个节点、右子树有 3 个节点。由于前序和中序遍历来自同一棵树左子树在前序里也必然恰好有 1 个节点。于是前序序列[3, 9, 20, 15, 7]中去掉根节点 3 之后[9]就是左子树的前序序列[20, 15, 7]就是右子树的前序序列。可以把这个逻辑概括成三步取前序区间第一个元素作为根节点。在中序区间中找到根的位置算出左子树长度leftSize indexOfRoot - inLeft。根据leftSize把前序区间切分为左、右两段同步把中序区间切分为左、右两段然后递归处理。这里最需要想明白的事情是我们不是把两个序列分别拍脑袋切分而是通过中序序列求出左子树大小再用这个大小去切分前序序列。中序序列是标尺前序序列是待切分的对象。这个主次关系一旦搞反代码必然写错。2.4 手工推演一个完整示例我建议你先手推一遍再去看代码。拿preorder [3, 9, 20, 15, 7]、inorder [9, 3, 15, 20, 7]举例前序第一个元素是 3根节点为 3。在中序里3 的下标是 1因此左子树长度为 1右子树长度为 3。前序序列切分左子树前序[9]右子树前序[20, 15, 7]。中序序列切分左子树中序[9]右子树中序[15, 20, 7]。递归左子树前序[9]第一个元素是 9中序[9]中 9 的下标是 0左子树长度为 0右子树长度为 0返回节点 9。递归右子树前序[20, 15, 7]第一个元素是 20中序[15, 20, 7]中 20 的下标是 1左子树长度为 1右子树长度为 1。前序切分为[15]和[7]。继续递归15 和 7 分别成为 20 的左右孩子。最终得到树结构根 3左孩子 9右孩子 2020 的左孩子 15右孩子 7。你把原数组画一下会发现这棵树完全符合前序和中序的遍历结果。2.5 递归式公式化表达如果用递归公式描述可以得到非常对称的结构build(preorder, inorder)根节点为preorder[0]左子树 build(preorder[1:1leftSize], inorder[:leftSize])右子树 build(preorder[1leftSize:], inorder[leftSize1:])其中leftSize是根节点在中序序列中的下标。这个公式写出来之后你会发现整道题的核心就是根据中序求 leftSize再用 leftSize 重排子问题。其他的一切都是套路化的递归模板。3. 从递归版到精细实现边界条件与索引计算的三个经典坑原理讲清楚了代码可以写得非常短。LeetCode 105 的标准递归版 Python 实现只有二十多行但就是这二十多行代码包含了三个非常容易出现 bug 的细节。很多人递归思路是对的代码跑起来却各种报错下面这节专门拆解。3.1 基线递归实现先能跑通再说优化先给出最直观的写法使用数组切片的版本便于理解class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def buildTree(preorder, inorder): if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) mid inorder.index(root_val) left_size mid root.left buildTree(preorder[1:1 left_size], inorder[:mid]) root.right buildTree(preorder[1 left_size:], inorder[mid 1:]) return root这段代码的思路完全对应上面推导的三个步骤先建立循环不变量preorder[0]就是当前子树的根inorder.index(root_val)告诉我们根在中序的位置left_size是中序中位于根左边的元素个数也就是左子树节点数量。注意这里的preorder[1:1 left_size]用的终点是1 left_size而不是left_size。很多人在这一步写错导致左右子树节点分配错乱。原因是前序序列中第一个元素已经被根节点占掉了所以左子树要从下标 1 开始取取left_size个元素时结束下标是1 left_sizePython 切片左闭右开。3.2 索引偏移的完整推导从切片版到区间版切片版虽然好理解但每次递归都要新建数组时间和空间都不理想。更标准的面试写法是使用索引区间只传左右边界不拷贝数组def buildTree(preorder, inorder): def helper(pre_left, pre_right, in_left, in_right): if pre_left pre_right: return None root_val preorder[pre_left] root TreeNode(root_val) mid inorder.index(root_val, in_left, in_right 1) left_size mid - in_left root.left helper(pre_left 1, pre_left left_size, in_left, mid - 1) root.right helper(pre_left left_size 1, pre_right, mid 1, in_right) return root return helper(0, len(preorder) - 1, 0, len(inorder) - 1)这里的四个边界要逐一理解任何一个出错都会导致完全不同的错误pre_left 1前序区间第一个元素是根左子树从下一个元素开始。pre_left left_size左子树在前序区间中占据left_size个位置因此终止下标是pre_left left_size。pre_left left_size 1右子树在左子树结束后的下一个位置开始。mid - 1和mid 1中序中根已经把左右子树隔开左子树区间终点是mid - 1右子树区间起点是mid 1。我当年学这道题时最大的困惑是为什么pre_right在左右子树的递归中似乎限制不住什么后来想明白了前序区间的右边界其实是由中序推导出的left_size间接约束的pre_right只是一个兜底边界。你可以把pre_right理解成总区间的保障线真正决定左右子树切分的是那个从中序根位置求得的left_size。3.3 经典坑一递归终止条件写错最常见的错误版本是这么写的if not preorder: return None如果你用切片版这个写法有时碰巧能跑对但如果你用区间版就完全不对。区间版必须用if pre_left pre_right来判断因为即使pre_left pre_right说明区间里还有且仅有一个节点此时需要创建节点并继续递归虽然左右子树会立即遇到终止条件。更隐蔽的问题是如果终止条件写成if not inorder在区间版代码中inorder永远不为空会导致无限递归最终抛出RecursionError。后面错误排查那一节我会专门展示我怎么定位这类问题的。一个非常有效的心法写终止条件前先想一想这个条件在叶子节点上的行为。叶子节点的特征是pre_left pre_right此时应当继续执行到创建节点然后左右子递归各自进入终止分支。如果条件写得让叶子节点无法创建那就是错的。3.4 经典坑二left_size的取值基准left_size必须等于mid - in_left而不是mid。这同样非常容易错。为什么当递归深入到右子树时in_left可能不是 0。比如上面的例子中右子树的中序区间是[15, 20, 7]若以in_left 3、in_right 5表示根 20 的下标mid 4那么左子树大小是4 - 3 1也就是节点 15。如果你偷懒写成left_size mid得到的左子树大小是 4完全错误。mid - in_left的含义是根节点在中序区间内左侧还有多少个节点这个偏移量必须相对于当前区间的左边界计算。画图时建议在纸上把in_left、mid、in_right三个指针标出来看mid左边有几格那个数字就是left_size一目了然。3.5 经典坑三切片版性能陷阱切片版虽然能跑通但有一个隐藏得很深的性能问题preorder[1:1 left_size]和inorder[:mid]每次递归都会产生新的列表。对于一棵链表形态的退化树每个节点只有一个孩子递归深度是 n每层都要拷贝剩余的所有元素总时间复杂度会退化到 O(n^2)。LeetCode 的测试用例通常不会让简单的切片版超时但面试中如果被追问你能优化吗只会切片版就很尴尬。我的建议是理解阶段用切片版确认思路后立刻改写成区间版。不要觉得这是两套代码它俩的区别只是用数组拷贝传递子问题和用边界标志传递子问题逻辑完全一致。4. 迭代式构建与哈希优化从正确到高效递归版写出来之后面试官通常会顺着问两个方向一是时间能不能再优化二是递归能不能改成迭代。这两个问题都有标准答案下面分别展开。4.1 哈希表优化把中序查找从 O(n) 降到 O(1)前面写的递归版每次都要inorder.index(root_val)这一步的时间是 O(n)。整棵树的时间复杂度为 O(n²)。优化方法非常直观用哈希表预处理中序序列中每个值对应的下标之后每次查找变成 O(1)。def buildTree(preorder, inorder): index_map {val: idx for idx, val in enumerate(inorder)} def helper(pre_left, pre_right, in_left, in_right): if pre_left pre_right: return None root_val preorder[pre_left] root TreeNode(root_val) mid index_map[root_val] left_size mid - in_left root.left helper(pre_left 1, pre_left left_size, in_left, mid - 1) root.right helper(pre_left left_size 1, pre_right, mid 1, in_right) return root return helper(0, len(preorder) - 1, 0, len(inorder) - 1)这里的index_map利用了题目中无重复元素的条件。如果存在重复值这种映射就不安全因为同一个值可能对应多个中序下标。优化后每个节点恰好被处理一次总时间复杂度为 O(n)空间复杂度为 O(n)哈希表 递归栈。提示面试中问到这题时我会直接写出哈希版本然后顺手解释一句我预先用哈希表记录中序位置让每次查找从线性变为常数级。这比先写 O(n²) 再在提示下优化印象分高很多。4.2 迭代构造法用栈模拟递归的推进顺序迭代版相比递归版要难理解得多但它是很多面试官考察递归转迭代能力的基准题。LeetCode 官方题解给过一种基于栈和指针的写法我来拆解它的核心思想。先放代码def buildTree(preorder, inorder): if not preorder: return None root TreeNode(preorder[0]) stack [root] inorder_idx 0 for pre_val in preorder[1:]: node TreeNode(pre_val) if stack[-1].val ! inorder[inorder_idx]: stack[-1].left node else: while stack and stack[-1].val inorder[inorder_idx]: last stack.pop() inorder_idx 1 last.right node stack.append(node) return root这段代码的思路非常精巧维护一个栈保存当前路径上尚未处理完右子树的节点。遇到新的前序节点时如果栈顶元素的值不等于当前中序指针指向的值说明新节点在左边继续挂左孩子如果相等说明左子树已经走到底需要不断回溯弹出直到找到一个节点把新节点挂到它的右孩子上。用一个具体例子推演preorder [3, 9, 20, 15, 7]inorder [9, 3, 15, 20, 7]初始化root3栈[3]inorder_idx0中序第一个值 9。处理 9栈顶 3 不等于中序指针指向的 9所以 9 成为 3 的左孩子栈变为[3, 9]。处理 20栈顶 9 等于中序指针指向的 9弹出 9inorder_idx 变为 1此时栈顶 3 仍等于中序指针指向的 3inorder[1] 3继续弹出 3inorder_idx 变为 2栈空跳出循环。把 20 挂到 last即 3的右孩子栈变为[20]。处理 15栈顶 20 不等于中序指针指向的 15inorder[2] 1515 成为 20 的左孩子栈变为[20, 15]。处理 7栈顶 15 等于中序指针指向的 15弹出 15inorder_idx 变为 3此时栈顶 20 等于 inorder[3] 20弹出 20inorder_idx 变为 4栈空跳出循环。把 7 挂到 last即 20的右孩子栈变为[7]。最终树结构3 的左孩子 9右孩子 2020 的左孩子 15右孩子 7。这个算法的本质是前序序列决定节点创建顺序中序序列决定什么时候左子树到底了该回去处理右子树。栈回溯的那个 while 循环就是在模拟递归中从深层调用返回上层的过程。虽然这个版本在所有情况下都是 O(n) 时间和 O(n) 空间但它对新手并不友好。我建议先花两三个晚上把递归版彻底写熟再来看迭代版。不要试图一上来就背迭代代码。4.3 三种方案的复杂度对照方案时间空间适用场景递归 中序线性查找O(n²)O(n)教学演示思路最直观递归 哈希映射O(n)O(n)面试标准回答工程首选迭代 栈O(n)O(n)考察递归转迭代能力避免深层递归栈溢出从实际面试的角度面试官认可的标准答案一般是递归 哈希映射。迭代版可以作为加分项展示但如果你讲不清楚它的指针移动逻辑建议不要主动展开免得被追问到细节时露怯。4.4 递归深度一个工程里绕不开的问题递归版有一个天然短板如果二叉树退化成一条链例如每个节点只有右孩子递归深度等于节点数。Python 默认递归深度限制是 1000 左右超过就会抛出RecursionError。遇到这种极端测试用例递归版即使时间上是 O(n) 也无法通过。解决思路有三种手动调大递归限制sys.setrecursionlimit(10000)但只适用于可预见的有限深度。改用迭代版彻底避开递归深度问题代价是代码更复杂。通过平衡策略处理如果树本身可能很深可以考虑先通过前序或中序信息做相关判断或者转向其他建树算法。LeetCode 的测试用例一般不会刻意构造万级递归深度的退化树但真实工程里的二叉树比如文件系统目录树、编译器 AST完全可能非常深。刷题时是AC 就行到了工程项目里递归深度是必须提前评估的风险点。5. 工程联想序列化、AST解析与由序建树的更广阔舞台LeetCode 105 看起来是一道纯粹的刷题但由遍历序列重建树的思想在多个工程方向都能找到影子。这一节我会把脑子里能关联到的方向全部串起来讲一遍让你明白这题为什么值得深挖。5.1 序列化反序列化树的存与取在实际业务中经常需要把一棵树保存到数据库或传输给前端。经典的 LeetCode 297 题就要求设计二叉树的序列化与反序列化方案。一个常用的序列化方案是前序 标记空节点反序列化时按前序顺序递归建树——这正是 105 题的递归建树思路。如果采用前序 中序的组合存储理论上也能还原二叉树代价是需要同时保存两个序列空间占用翻倍。而用前序 空节点标记的方式只需要一个序列。这两种方法有很多共通点序列化决定如何把结构信息压平反序列化决定如何从压平的数据恢复结构而前序定根、中序定左右就是最经典的还原协议之一。5.2 表达式求值与 AST 构建编译器设计课上有一道很经典的练习把中缀表达式a b * c转成抽象语法树AST。这里最朴素的算法其实与由序遍历建树异曲同工操作符相当于根节点操作数相当于叶子节点优先级决定树的层级结构。只不过表达式场景下遍历序列不是显式给定的而是藏在表达式字符串中的。更直接的联系出现在根据前序表达式建树的场景前缀表达式波兰式 a * b c本身就是一棵表达式树的前序遍历结果。要把前缀表达式还原成树我们同样需要前序定根的规则——只不过在这里节点有多少个孩子是由操作符的元数一元还是二元决定的而不是由中序序列决定的。回到 LeetCode 105如果你理解前序用来找根中序用来确定左右子树的边界那你在理解前缀表达式 操作符元数确定子树边界时就会觉得非常顺畅。两者的递归骨架是同一个。5.3 数据库索引与文件系统的重建联想B 树索引在教科书里经常用排序后的键值序列表示叶子节点中间层则记录了索引路径。虽然 B 树的物理存储与普通二叉树不同但从一个线性序列中恢复层级结构的思想是共通的。文件系统目录树的持久化与恢复XML/JSON 的 DOM 树解析也都在做类似的序列-结构的还原。我并非建议你去刷 B 树题目而是想说当你掌握了一种由序列还原结构的思维模型以后遇到任何涉及展开/压缩的数据格式都会条件反射地想到哪部分序列在提供结构信息哪部分序列在提供节点内容。这种条件反射是在工程中快速定位问题的重要能力。5.4 姊妹题对比106、889 与搜索二叉树的特殊情形LeetCode 105 学完之后强烈建议立刻做这三道题LeetCode 106从中序与后序遍历序列构造二叉树。思路完全对称后序的最后一个元素是根同样用中序求出左右子树大小。LeetCode 889从前序和后序遍历序列构造二叉树。这道题有一点特殊前序 后序通常不能唯一确定一棵二叉树只有当树是满二叉树每个节点要么没有孩子要么有两个孩子时才唯一。题目一般会给出一个可以返回任意合法答案的宽松条件。LeetCode 1008前序遍历构造二叉搜索树。因为搜索二叉树的左子树所有值都小于根、右子树所有值都大于根仅凭前序序列就能还原出唯一一棵树。这可以看作 105 的一个变体不需要中序序列因为值的大小关系天然提供了左右子树的边界。做完这三道题你会发现由序遍历建树这个主题下所有的变化核心都是同一个问题如何在当前序列中找到左子树与右子树的切分点。中序序列提供了清晰的切分线后序/前序提供了根的位置搜索二叉树用数值的大小关系替代中序序列前序后序则只适合特殊形态的树。顺便提一句前面热搜词里提到的线索二叉树也和中序遍历密切相关。线索二叉树利用空指针记录前驱后继本质上是在不增加额外空间的情况下把二叉树的中序遍历序列化到节点结构里。它和本题共享中序序列是树的线性投影这个底层认知。6. 错误排查实战从报错信息反推索引与递归问题二叉树递归程序报错是很多新人最头疼的事。这一节我们不讲正确代码专门讲错误代码为什么错、怎么定位。我从自己辅导过的真实案例里挑出三类最高频的错误逐个走一遍排查链路。6.1 典型报错一IndexError: list index out of range用户写了一个区间版的递归跑测试用例时直接报错IndexError: list index out of range第二步我让他把每个递归分支的pre_left和pre_right打印出来重点看最后一次递归前打印了什么。他贴出的输出里最后一次出现了pre_left4, pre_right3说明终止条件没有拦住这种情况。继续检查他的终止条件发现他写的是if in_left in_right: return None问题就出在这里他只检查了中序区间边界没有检查前序边界。在中序序列里根节点可能在区间最左侧或最右侧此时对应的左子树或右子树确实会在中序中提前为空in_left in_right因此这个条件看起来合情合理。但前序的区间变空通常发生在父节点递归调用时索引偏移计算错误的情况下而不是正常变空。正确的修法有两种要么补上if pre_left pre_right: return None要么直接用left_size来约束递归保证前序区间必然与中序区间同步变空。这个案例的关键教训在于递归终止条件必须在每个递归参数维度上都成立不能只依赖其中一个。二叉树递归函数通常有多个边界参数写终止条件时要一一对账。6.2 典型报错二RecursionError: maximum recursion depth exceeded另一个高频报错是无限递归导致的栈溢出RecursionError: maximum recursion depth exceeded这类错误的典型原因是递归参数没有向终止条件收敛。举个例子有人写出过这样的代码def helper(preorder, inorder): if not preorder: return None root_val preorder[0] root TreeNode(root_val) mid inorder.index(root_val) root.left helper(preorder[1:], inorder[:mid]) root.right helper(preorder[1:], inorder[mid1:]) return root这段代码左右子树都传了preorder[1:]等于说左子树得到了整棵右子树的前序序列递归时mid位置永远对不上子问题大小无法正确缩小最终栈溢出。排查思路很简单在递归函数第一行打印当前 preorder 和 inorder 的长度观察是否在逐层缩小。如果连续多次长度不变一定是切分逻辑错了。LeetCode 网页端也可以直接在本地 IDE 中打断点单步查看每次递归时传入的数组内容比盯着报错信息猜要快得多。6.3 典型报错三代码不报错树却构建错误最气人的一种情况是程序运行正常结果提交却 Wrong Answer。这时候需要一种快速验证树结构的方法。我通常的做法是写一个层序遍历打印函数from collections import deque def level_order(root): if not root: return [] result [] queue deque([root]) while queue: node queue.popleft() result.append(node.val if node else None) if node: queue.append(node.left) queue.append(node.right) return result构造完成后用level_order(buildTree(preorder, inorder))和预期树逐层对比。比如preorder[1,2,3], inorder[3,2,1]如果层序结果是[1,2,None,3]或[1,2,3]分别能帮你判断是哪一侧挂错了节点。不过这种方法有个局限遇到 None 节点之后它的子孙不会继续入队因此只能验证大致结构无法验证完整树形。更严谨的做法是打印前序和中序的还原结果比对是否和输入一致——树的遍历结果相同几乎可以确定结构正确。6.4 一个通用的二叉树递归调试清单我把这些经验整理成一份自查清单写任何二叉树递归题时对照使用终止条件是否覆盖了所有递归参数特别是pre_left和in_left是否同步判断了根节点的取值位置是否正确前序取左边界后序取右边界中序取中间位置。left_size是否相对于当前in_left计算而不是直接用mid左右子树的索引偏移是否加上了根节点占用的位置每个递归调用是否会让子问题的规模严格小于父问题这五条如果全部回答是你的递归代码大概率不会出现 6.1 到 6.3 中的问题。7. 个人经验总结这道题我建议你这样刷很多人问我LeetCode 105 到底要刷几遍才算掌握我自己的标准是能不看任何参考十分钟内在空白编辑器中写出带哈希优化的递归版同时能清楚解释每一处索引偏移的含义。达到这个标准才叫会了。从实操安排上我建议按下面这个路线走第一遍按本文第 2 节的推演过程手工在纸上还原至少三棵不同形态的树确保理解前序定根、中序分界、leftSize 作桥这三个核心要点。第二遍写切片版递归跑通基础用例感受最直观的写法长什么样。第三遍改成区间版递归对照第 3 节列出的三个坑逐一检查并且故意写错一处、观察报错锻炼自己根据报错定位问题的能力。第四遍加哈希优化提交通过然后口头向自己解释时间复杂度的变化。完成以上四遍之后再去做 106 和 889一定会发现思路清晰得多。因为这三道题的递归骨架是同一个区别只在于根在后序的哪个位置以及中序要如何配合。在文章末尾想分享一个小技巧做完 105 之后我习惯把前序、中序、后序、层序遍历的代码都写在同一页然后观察四种遍历序列在相同树上的输出。看到前序和中序如何从不同角度记录同一棵树很多递归的直觉就是这么练出来的。希望这篇文章能帮你少走一些弯路早日把这题变成闭眼能写的题。