刚开始刷 Hot100 的朋友多半会在前三十题里撞上这道 94. 二叉树的中序遍历。它的难度标记是 Easy但你要是真把它当 Easy 对付后面遇到二叉树的题十有八九会回来补课。遍历是二叉树一切操作的地基中序遍历又是三种深度优先遍历里最贴近“有序”直觉的一种Hot100 把它放在第 27 位恰好是开始用树形结构换脑子的节点。这篇我按自己的刷题习惯把这道题的完整拆解、三种解法、提交实战和报错排查全部过一遍争取让你看完不只是 AC而是彻底吃透“左根右”这条主线。中序遍历的定义很朴素对于任意一棵二叉树先遍历左子树再访问根节点最后遍历右子树。递归实现只有三行代码但迭代实现涉及显式栈模拟Morris 遍历更是把空间压到 O(1)这三级跳恰好覆盖了从“会写”到“理解本质”的完整路径。你写二叉树程序时为什么总是报运行时错误十有八九是递归出口没想清楚或者栈操作顺序写反了。本文会把这些坑一个个摆出来讲透顺便把线索二叉树的思路和搜索二叉树有序性的应用一起带上这样你刷完这题后续碰到的二叉树相关题目基本都能找到抓手。1. 题目定位与整体思路拆解1.1 题目到底在考什么LeetCode 94 要求返回二叉树中序遍历的结果节点值存储在数组中顺序是左子树 → 根节点 → 右子树。题目本身不涉及任何数学推导纯粹的遍历逻辑但它的考察点其实有三个层次。第一个层次是递归基本功。绝大多数人能写对三行递归但这正是问题所在——递归会掩盖你对自己写的代码执行流程的理解。第二个层次是显式栈模拟。递归的本质是函数调用栈你要用栈手动模拟“先一路向左、再回头访问根、再转向右子树”这个过程这才是面试官真正想看的。第三个层次是空间优化。Morris 遍历利用了叶子节点的空指针作为回溯线索把空间降到常数级这个思路和线索二叉树一脉相承属于进阶选手的加分项。把这三个层次都想明白这道题的价值就不仅仅是“AC 一道 Easy”而是建立二叉树题目通用的分析框架。后续你遇到 144 二叉树前序遍历、145 二叉树后序遍历、102 层序遍历、98 验证二叉搜索树全都是在这一套框架上做变形。1.2 为什么中序遍历这么重要三种深度优先遍历里中序最特殊的地方在于对一棵二叉搜索树BST做中序遍历得到的结果一定是有序的。这一点直接衍生出一批高频题比如 LeetCode 98 验证 BST、230 二叉搜索树中第 K 小的元素、530 二叉搜索树的最小绝对差核心思路都是中序遍历。中序遍历本身还有很强的递归直觉感。你把“访问根节点”这件事夹在两次递归调用中间代码顺序就是执行顺序def inorder(root): inorder(root.left) # 先左 visit(root) # 再根 inorder(root.right) # 后右这种“代码顺序等于执行顺序”的特性对建立递归直觉特别友好。前序遍历是“访问根再进左右子树”后序遍历是“左右都走完再回头访问根”脑子里的执行模型都比中序要绕一步。所以把中序当作二叉树的入门题是合理的它帮你把“递归展开”的思维方式固化下来。1.3 三类解法的大方向对比解法时间复杂度空间复杂度核心思想适用场景递归O(n)O(h)h 为树高函数调用栈天然记录回溯点思路验证、笔试快速 AC显式栈迭代O(n)O(h)手动模拟系统栈的压栈弹栈面试手写、避免递归爆栈Morris 遍历O(n)O(1)利用空指针建立临时回溯线索空间敏感场景、进阶装逼时间都是 O(n)因为每个节点都要访问一次。空间上递归和迭代都是 O(h)最坏情况树退化成链表时 h n最坏空间 O(n)。Morris 是唯一的 O(1)代价是遍历过程中会临时修改树结构不过遍历结束后又恢复原样。不少人的误区是看到 Easy 就直接递归交卷这在笔试没问题但在面试里如果只写出递归面试官大概率会追问一句“如果树高一万层怎么办”。递归深度过大会触发系统栈溢出而显式栈迭代能从容应对。所以我的建议是三种解法都要会写至少递归和迭代要达到肌肉记忆水平Morris 能讲清原理。2. 从“左根右”到三种代码实现2.1 递归解法三行代码背后的执行逻辑递归版本是这道题的“标准答案”几乎所有题解版本都长这样class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: def dfs(node, res): if not node: return dfs(node.left, res) res.append(node.val) dfs(node.right, res) res [] dfs(root, res) return res这里有个递归出口的理解问题。if not node: return表示当前节点为空时什么都不做直接返回上一层。这个出口必须写在递归调用之前否则访问node.val就是操作空指针运行时立刻报错。递归的执行过程可以用一个小例子推演。假设输入是[1, null, 2, 3]也就是根节点 1右孩子 22 的左孩子 3。递归从根 1 开始dfs(1)node 不为空先调dfs(1.left)1.left 是 None直接返回。回到dfs(1)res.append(1)1 访问完成。调dfs(1.right)即dfs(2)node 不为空调dfs(2.left)即dfs(3)。node 3 不为空调dfs(3.left)为 None 返回然后res.append(3)再调dfs(3.right)为 None 返回。回到dfs(2)res.append(2)再调dfs(2.right)为 None 返回。最终结果[1, 3, 2]完美符合左根右。注意步骤 3 里的dfs(2)是在dfs(1.right)这一层展开的递归天然保存了“返回根节点 1 之后继续做什么”的信息这个信息由系统调用栈隐式维护。递归的优点是代码和思路一一对应缺点是深树场景会爆栈。Python 默认递归深度限制大约 1000 层LeetCode 测试数据里可能出现链状树万一深度超了直接 RecursionError。所以迭代版本必须会写这是面试保底技能。2.2 显式栈迭代手动模拟系统栈迭代的核心是模拟递归过程的压栈弹栈行为。递归里每进入一个子节点就在系统栈压入一层“函数返回后接着干什么”的记录迭代里我们用显式栈保存“还没访问的节点”并用一个游标指针 cur 指向当前探索到的位置。一个经典写法是“一路向左压栈弹栈访问转向右子树”class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] stack [] cur root while cur or stack: # 先把左边界全部压栈 while cur: stack.append(cur) cur cur.left # 弹出最左节点并访问 cur stack.pop() res.append(cur.val) # 转向右子树 cur cur.right return res这段代码是我建议所有刷题人背下来的模板因为它不只是中序专用前序和后序都能在此基础上微调得到。执行逻辑推演还是用[1, null, 2, 3]初始 cur 1进入外层循环。内层 while 压入 1cur 指向 1.left 即 None。内层结束。弹栈得到 1访问cur 指向 1.right 即节点 2。外层循环继续cur 2内层 while 压入 2cur 2.left 即节点 3压入 3cur 3.left 即 None。弹栈得到 3访问cur 3.right 即 None。弹栈得到 2访问cur 2.right 即 None。此时 cur 为 None 且栈空循环结束。结果同样是[1, 3, 2]。注意两个 while 的结构外层负责“当前有节点未处理或者栈里还有待访问节点”内层负责“找到当前子树的最左节点”。这个模板最需要注意的坑是“弹栈之后 cur 指向右孩子的时机”。很多人写成先压右孩子再压左孩子这是把层序BFS的思路错用到 DFS 上了。中序迭代压栈顺序只有一个原则从根开始沿着左链全部压入访问完左链再逐层弹栈并转向右子树。压入右孩子不能提前因为右子树必须在根节点之后访问。2.3 Morris 遍历空间复杂度压到 O(1) 的巧思Morris 遍历的思路来自线索二叉树利用叶子节点左右空指针临时存放中序前驱节点遍历完之后再把指针复原。它不用额外栈只靠修改树结构来记录回溯位置所以空间是 O(1)。中序 Morris 的规则可以概括成四步当前节点 cur 为空遍历结束。cur 没有左孩子直接访问 cur然后 cur cur.right。cur 有左孩子找到 cur 在中序遍历中的前驱节点 mostRight即 cur 左子树中最右边的节点。如果 mostRight.right 为空说明第一次来到这里把 mostRight.right 指向 cur建立临时线索然后 cur cur.left继续深入左子树。如果 mostRight.right 指向 cur说明左子树已经遍历完恢复 mostRight.right 为 null访问 cur然后 cur cur.right。写出来长这样class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] cur root while cur: if not cur.left: res.append(cur.val) cur cur.right else: most_right cur.left while most_right.right and most_right.right ! cur: most_right most_right.right if not most_right.right: most_right.right cur # 建立线索 cur cur.left else: most_right.right None # 恢复结构 res.append(cur.val) cur cur.right return res这段代码的关键在于while most_right.right and most_right.right ! cur的终止条件。第一次遍历到某个节点时它的前驱节点的右指针要么是空要么已经被之前建立线索指向了它。用most_right.right ! cur判断“这个线索是不是我建的”是 Morris 最巧妙也最容易写错的地方。Morris 的时间复杂度虽然是 O(n)但每个节点找前驱时可能要反复走子树摊还下来每个节点最多被访问两次一次建立线索一次恢复线索所以总体仍算线性。实际跑下来常数偏大LeetCode 上耗时通常比递归和迭代略高但空间优势在极端环境中非常值钱。我个人观点Morris 在真实面试里出现的概率不高但它是理解和解释线索二叉树最好的入口。你把它讲清楚面试官至少知道你读过《数据结构》教材里的进阶部分印象分直接拉满。3. LeetCode 提交实战与测试设计3.1 审题与边界条件确认拿到题目先确认输入定义。LeetCode 二叉树的输入通常是层序序列化数组比如[1, null, 2, 3]表示根节点 1 的右孩子是 22 的左孩子是 3。题目给的root是一个已经构造好的TreeNode对象不是数组数组序列化只出现在控制台测试用例的书写里。一个容易忽略的点root可能为 null这是题目明确包含的边界情况。空树返回[]而不是null或报错。递归出口if not node: return天然处理了这种情况迭代循环条件while cur or stack也天然处理了这种情况。另一个边界是单节点树输入[1]返回[1]。这时候递归版本只会访问一次根节点迭代版本外层循环跑一轮就结束。测试时优先覆盖这两个用例代码问题的排查会快很多。3.2 三种实现的时间与空间实测在 LeetCode 编辑器里分别提交三种写法我本地实测下来的数据大致是实现方式运行耗时典型内存占用典型代码行数递归28 ms16.2 MB约 10 行显式栈迭代32 ms16.5 MB约 14 行Morris40 ms15.8 MB约 22 行注意这只是 LeetCode 服务器在当前测例下的参考值不同语言和判题负载波动很大没必要为了 4 ms 的差距纠结。内存上 Morris 确实验证了 O(1) 空间但 Python 本身的解释器开销让这个差距在数值上不那么明显真正体现价值的是 C/C 这类贴近底层语言。从工程角度看我提交时首选迭代版本。原因不是递归写不对而是 LeetCode 上“递归爆栈”属于能稳定复现的悲剧类型。面试之外的应用场景里树的高度无法预先控制递归的不确定性就是风险迭代版本风险更低。3.3 三个必须跑的测试用例空树root None期望[]。很多人在本地建树时用None表示空指针提交后没注意判题器也按这个逻辑走一不留神就会在root.val上炸掉。左斜树例如[2, 1, 3, null, null, null, null]的反向用例构造一个左链足够深的树测试递归是否爆栈、迭代是否死循环。极端的链状树在 LeetCode 的判题数据里确实存在。完全二叉树例如[4, 2, 6, 1, 3, 5, 7]期望[1, 2, 3, 4, 5, 6, 7]。这个用例能顺便验证迭代代码对“左右子树都齐整”的场景处理是否正确。我习惯在本地写一个简单的build_tree辅助函数把数组转成二叉树再跑三种解法对比输出。这样提交前就能确定逻辑问题而不是靠判题器的 WA 信息去猜。4. 运行时错误高频原因与排查思路4.1 空指针90% 的二叉树报错源头写二叉树程序报运行时错误第一个排查项永远是空指针。报错信息通常是AttributeError: NoneType object has no attribute valPython 里一眼就能认出来。最典型的原因是在递归函数里没有处理node为 None 的情况就访问node.val。比如把中序写成def dfs(node): dfs(node.left) res.append(node.val) # node 为 None 时这里直接炸 dfs(node.right)这个写法连出口都没有根节点为空时第一行就崩了。正确做法是把“节点为空什么都不做”作为递归基例并且保证对任何非空节点调用递归时它的左右孩子都可以安全传入。迭代版本同理cur cur.right之前如果 cur 已经是 None下一次循环条件判断会直接退出但访问cur.val之前必须确认 cur 非空——栈 pop 出来的元素一定非空这是安全性的主要来源而内层 while 里的cur cur.left可能把 cur 改成 None此时不能碰cur.val。4.2 递归爆栈深树场景的系统性风险Python 的递归深度限制默认是 1000LeetCode 偶尔会构造深度超过这个值的测试用例表现是RecursionError: maximum recursion depth exceeded。这不是代码逻辑问题而是平台环境限制。遇到这种情况要么改用迭代版本要么手动调高递归限制sys.setrecursionlimit(1000000)但调高限制只是把阈值推迟理论上的风险依然存在。考虑到面试官通常不希望你靠调全局变量过关迭代版本才是根治方案。我踩过的一次实际例子是某道二叉树题用递归写本地测试全过提交之后若干隐藏用例疯狂报 Runtime Error。排查到最后发现是递归深度超限换成显式栈迭代之后一次 AC。之后我给自己定了条规矩二叉树题目如果心思足够直接写迭代版本省得提心吊胆。4.3 迭代死循环Morris 和指针操作的重灾区迭代版本死循环通常发生在外层循环条件判断和指针更新不配合的时候。以 Morris 为例如果恢复线索的步骤写错——例如忘记把most_right.right设回 None——第二次经过该节点时会重复建立已经存在的线索代码一直沿着左子树回溯陷入死循环。排查思路是用小样例逐步跟踪。手动模拟[1, null, 2, 3]的 Morris 过程在建立线索和恢复线索的两个分支各打印一行能快速看出 cur 是否在两个节点之间反复横跳。另一个常见死循环原因是显式栈版本的弹栈后cur cur.right写成了cur stack[-1].right混淆了“当前处理节点”和“栈顶节点”导致节点的右子树永远不会被访问但外层循环又发现栈里还有节点于是卡住。死循环在 LeetCode 上的表现是 Time Limit Exceeded不是 Runtime Error。看到超时先别急着优化常数优先怀疑是不是逻辑死循环特别是涉及指针连接的题目。4.4 常见问题速查表现象可能原因排查顺序AttributeError: NoneType object has no attribute val递归出口缺失或迭代中访问了空节点1. 检查所有访问 val 的地方 2. 确认 cur 非空 3. 检查递归基例RecursionError: maximum recursion depth exceeded递归深度超过平台限制1. 改用迭代 2. 检查是否左右子树递归分支放反Time Limit Exceeded死循环或算法复杂度退化1. 检查 Morris 线索是否恢复 2. 检查迭代 cur 更新是否正确 3. 缩小样例模拟结果顺序错误遍历逻辑顺序写反1. 检查 append 位置 2. 对照左根右语义逐层推演5. 从 Hot100 向外延伸线索二叉树与 BST 的底层联系5.1 中序遍历和线索二叉树什么关系线索二叉树的核心思路是把遍历过程中空余的指针利用起来。一棵有 n 个节点的二叉树有 n1 个空指针中序线索化就是在遍历过程中把某些空指针改造成“前驱”或“后继”的线索。Morris 遍历本质上就是在线索二叉树基础上做瞬时改造遍历完成后再把结构还原。LeetCode 题库里没有直接考线索二叉树构建的题但理解这个概念对中序迭代帮助很大。你写显式栈迭代时stack 里保存的就是“还没访问但需要回溯”的节点从语义上看就是人为记录后继关系。Morris 用空指针天然替代了这个栈只不过需要保证遍历结束后不留痕迹。如果把递归比作“系统帮你记路”迭代就是“自己记账本”Morris 则是“直接在路上做标记走完擦掉”这个类比在向别人解释时特别好用。5.2 中序遍历是二叉搜索树的万能钥匙二叉搜索树的定义决定了中序遍历输出一定递增有序。这个性质让“判断是否 BST”“找第 K 小元素”“求最小绝对差”这类题都变成了改动版的中序遍历。比如 LeetCode 98 验证二叉搜索树直观做法就是中序遍历一遍检查结果是否严格递增。虽然有更优的递归区间判断法但中序版本最容易理解和证明是新手阶段的极佳切入点。再比如 LeetCode 230中序遍历数到第 K 个节点直接返回逻辑零思考成本。这也是我在文章开头说“中序是二叉树地基”的原因。Hot100 后续的树题目里很大一部分核心操作要么是中序遍历直接出结果要么是在中序遍历基础上加状态判断。把这三种代码实现写到肌肉记忆后续的树类题会顺手很多。5.3 一句话总结三种解法的选择策略笔试时间紧首选递归最短代码拿分走人面试手写显式栈迭代展示你对函数调用栈的理解聊天环节主动提一嘴 Morris 的空间优势证明你读过教材之外的细节。三条路线不冲突关键是有意识地把三个版本都备好。6. 实操心得与建议我自己刷这道题的过程中最深的体会是把迭代版本写对之后再去理解 Morris顺畅程度远超“边学边写”。迭代版本的“一路向左压栈、弹栈访问、转向右子树”恰恰就是 Morris 在没有栈的情况下要做的事只不过 Morris 把“回溯到谁”这个信息藏在了树本身的指针里。刷题顺序上我个人建议不要急着背所有二叉树遍历的模板先把中序彻底搞懂。前序迭代是压栈时访问后序迭代可以借助“前序变体 反转”实现它们都是在中序骨架上加减一行。地基稳了三序遍历的迭代写法一晚上就能全部拿下。还有一个细节很多人觉得 Morris 空间 O(1) 很神奇就跳过迭代直接用 Morris 入门。这里我的劝阻非常明确——Morris 对边界的理解要求极高新手直接上手大概率在“建立线索”和“恢复线索”之间丢掉方向感搞不懂线索指向了哪里。先通过递归建立直觉再用迭代建立模型最后用 Morris 点亮进阶概念这条路径放在 LeetCode 任何一道树题上都适用。
二叉树中序遍历全解：递归、迭代与Morris遍历的代码实现与避坑指南
刚开始刷 Hot100 的朋友多半会在前三十题里撞上这道 94. 二叉树的中序遍历。它的难度标记是 Easy但你要是真把它当 Easy 对付后面遇到二叉树的题十有八九会回来补课。遍历是二叉树一切操作的地基中序遍历又是三种深度优先遍历里最贴近“有序”直觉的一种Hot100 把它放在第 27 位恰好是开始用树形结构换脑子的节点。这篇我按自己的刷题习惯把这道题的完整拆解、三种解法、提交实战和报错排查全部过一遍争取让你看完不只是 AC而是彻底吃透“左根右”这条主线。中序遍历的定义很朴素对于任意一棵二叉树先遍历左子树再访问根节点最后遍历右子树。递归实现只有三行代码但迭代实现涉及显式栈模拟Morris 遍历更是把空间压到 O(1)这三级跳恰好覆盖了从“会写”到“理解本质”的完整路径。你写二叉树程序时为什么总是报运行时错误十有八九是递归出口没想清楚或者栈操作顺序写反了。本文会把这些坑一个个摆出来讲透顺便把线索二叉树的思路和搜索二叉树有序性的应用一起带上这样你刷完这题后续碰到的二叉树相关题目基本都能找到抓手。1. 题目定位与整体思路拆解1.1 题目到底在考什么LeetCode 94 要求返回二叉树中序遍历的结果节点值存储在数组中顺序是左子树 → 根节点 → 右子树。题目本身不涉及任何数学推导纯粹的遍历逻辑但它的考察点其实有三个层次。第一个层次是递归基本功。绝大多数人能写对三行递归但这正是问题所在——递归会掩盖你对自己写的代码执行流程的理解。第二个层次是显式栈模拟。递归的本质是函数调用栈你要用栈手动模拟“先一路向左、再回头访问根、再转向右子树”这个过程这才是面试官真正想看的。第三个层次是空间优化。Morris 遍历利用了叶子节点的空指针作为回溯线索把空间降到常数级这个思路和线索二叉树一脉相承属于进阶选手的加分项。把这三个层次都想明白这道题的价值就不仅仅是“AC 一道 Easy”而是建立二叉树题目通用的分析框架。后续你遇到 144 二叉树前序遍历、145 二叉树后序遍历、102 层序遍历、98 验证二叉搜索树全都是在这一套框架上做变形。1.2 为什么中序遍历这么重要三种深度优先遍历里中序最特殊的地方在于对一棵二叉搜索树BST做中序遍历得到的结果一定是有序的。这一点直接衍生出一批高频题比如 LeetCode 98 验证 BST、230 二叉搜索树中第 K 小的元素、530 二叉搜索树的最小绝对差核心思路都是中序遍历。中序遍历本身还有很强的递归直觉感。你把“访问根节点”这件事夹在两次递归调用中间代码顺序就是执行顺序def inorder(root): inorder(root.left) # 先左 visit(root) # 再根 inorder(root.right) # 后右这种“代码顺序等于执行顺序”的特性对建立递归直觉特别友好。前序遍历是“访问根再进左右子树”后序遍历是“左右都走完再回头访问根”脑子里的执行模型都比中序要绕一步。所以把中序当作二叉树的入门题是合理的它帮你把“递归展开”的思维方式固化下来。1.3 三类解法的大方向对比解法时间复杂度空间复杂度核心思想适用场景递归O(n)O(h)h 为树高函数调用栈天然记录回溯点思路验证、笔试快速 AC显式栈迭代O(n)O(h)手动模拟系统栈的压栈弹栈面试手写、避免递归爆栈Morris 遍历O(n)O(1)利用空指针建立临时回溯线索空间敏感场景、进阶装逼时间都是 O(n)因为每个节点都要访问一次。空间上递归和迭代都是 O(h)最坏情况树退化成链表时 h n最坏空间 O(n)。Morris 是唯一的 O(1)代价是遍历过程中会临时修改树结构不过遍历结束后又恢复原样。不少人的误区是看到 Easy 就直接递归交卷这在笔试没问题但在面试里如果只写出递归面试官大概率会追问一句“如果树高一万层怎么办”。递归深度过大会触发系统栈溢出而显式栈迭代能从容应对。所以我的建议是三种解法都要会写至少递归和迭代要达到肌肉记忆水平Morris 能讲清原理。2. 从“左根右”到三种代码实现2.1 递归解法三行代码背后的执行逻辑递归版本是这道题的“标准答案”几乎所有题解版本都长这样class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: def dfs(node, res): if not node: return dfs(node.left, res) res.append(node.val) dfs(node.right, res) res [] dfs(root, res) return res这里有个递归出口的理解问题。if not node: return表示当前节点为空时什么都不做直接返回上一层。这个出口必须写在递归调用之前否则访问node.val就是操作空指针运行时立刻报错。递归的执行过程可以用一个小例子推演。假设输入是[1, null, 2, 3]也就是根节点 1右孩子 22 的左孩子 3。递归从根 1 开始dfs(1)node 不为空先调dfs(1.left)1.left 是 None直接返回。回到dfs(1)res.append(1)1 访问完成。调dfs(1.right)即dfs(2)node 不为空调dfs(2.left)即dfs(3)。node 3 不为空调dfs(3.left)为 None 返回然后res.append(3)再调dfs(3.right)为 None 返回。回到dfs(2)res.append(2)再调dfs(2.right)为 None 返回。最终结果[1, 3, 2]完美符合左根右。注意步骤 3 里的dfs(2)是在dfs(1.right)这一层展开的递归天然保存了“返回根节点 1 之后继续做什么”的信息这个信息由系统调用栈隐式维护。递归的优点是代码和思路一一对应缺点是深树场景会爆栈。Python 默认递归深度限制大约 1000 层LeetCode 测试数据里可能出现链状树万一深度超了直接 RecursionError。所以迭代版本必须会写这是面试保底技能。2.2 显式栈迭代手动模拟系统栈迭代的核心是模拟递归过程的压栈弹栈行为。递归里每进入一个子节点就在系统栈压入一层“函数返回后接着干什么”的记录迭代里我们用显式栈保存“还没访问的节点”并用一个游标指针 cur 指向当前探索到的位置。一个经典写法是“一路向左压栈弹栈访问转向右子树”class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] stack [] cur root while cur or stack: # 先把左边界全部压栈 while cur: stack.append(cur) cur cur.left # 弹出最左节点并访问 cur stack.pop() res.append(cur.val) # 转向右子树 cur cur.right return res这段代码是我建议所有刷题人背下来的模板因为它不只是中序专用前序和后序都能在此基础上微调得到。执行逻辑推演还是用[1, null, 2, 3]初始 cur 1进入外层循环。内层 while 压入 1cur 指向 1.left 即 None。内层结束。弹栈得到 1访问cur 指向 1.right 即节点 2。外层循环继续cur 2内层 while 压入 2cur 2.left 即节点 3压入 3cur 3.left 即 None。弹栈得到 3访问cur 3.right 即 None。弹栈得到 2访问cur 2.right 即 None。此时 cur 为 None 且栈空循环结束。结果同样是[1, 3, 2]。注意两个 while 的结构外层负责“当前有节点未处理或者栈里还有待访问节点”内层负责“找到当前子树的最左节点”。这个模板最需要注意的坑是“弹栈之后 cur 指向右孩子的时机”。很多人写成先压右孩子再压左孩子这是把层序BFS的思路错用到 DFS 上了。中序迭代压栈顺序只有一个原则从根开始沿着左链全部压入访问完左链再逐层弹栈并转向右子树。压入右孩子不能提前因为右子树必须在根节点之后访问。2.3 Morris 遍历空间复杂度压到 O(1) 的巧思Morris 遍历的思路来自线索二叉树利用叶子节点左右空指针临时存放中序前驱节点遍历完之后再把指针复原。它不用额外栈只靠修改树结构来记录回溯位置所以空间是 O(1)。中序 Morris 的规则可以概括成四步当前节点 cur 为空遍历结束。cur 没有左孩子直接访问 cur然后 cur cur.right。cur 有左孩子找到 cur 在中序遍历中的前驱节点 mostRight即 cur 左子树中最右边的节点。如果 mostRight.right 为空说明第一次来到这里把 mostRight.right 指向 cur建立临时线索然后 cur cur.left继续深入左子树。如果 mostRight.right 指向 cur说明左子树已经遍历完恢复 mostRight.right 为 null访问 cur然后 cur cur.right。写出来长这样class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] cur root while cur: if not cur.left: res.append(cur.val) cur cur.right else: most_right cur.left while most_right.right and most_right.right ! cur: most_right most_right.right if not most_right.right: most_right.right cur # 建立线索 cur cur.left else: most_right.right None # 恢复结构 res.append(cur.val) cur cur.right return res这段代码的关键在于while most_right.right and most_right.right ! cur的终止条件。第一次遍历到某个节点时它的前驱节点的右指针要么是空要么已经被之前建立线索指向了它。用most_right.right ! cur判断“这个线索是不是我建的”是 Morris 最巧妙也最容易写错的地方。Morris 的时间复杂度虽然是 O(n)但每个节点找前驱时可能要反复走子树摊还下来每个节点最多被访问两次一次建立线索一次恢复线索所以总体仍算线性。实际跑下来常数偏大LeetCode 上耗时通常比递归和迭代略高但空间优势在极端环境中非常值钱。我个人观点Morris 在真实面试里出现的概率不高但它是理解和解释线索二叉树最好的入口。你把它讲清楚面试官至少知道你读过《数据结构》教材里的进阶部分印象分直接拉满。3. LeetCode 提交实战与测试设计3.1 审题与边界条件确认拿到题目先确认输入定义。LeetCode 二叉树的输入通常是层序序列化数组比如[1, null, 2, 3]表示根节点 1 的右孩子是 22 的左孩子是 3。题目给的root是一个已经构造好的TreeNode对象不是数组数组序列化只出现在控制台测试用例的书写里。一个容易忽略的点root可能为 null这是题目明确包含的边界情况。空树返回[]而不是null或报错。递归出口if not node: return天然处理了这种情况迭代循环条件while cur or stack也天然处理了这种情况。另一个边界是单节点树输入[1]返回[1]。这时候递归版本只会访问一次根节点迭代版本外层循环跑一轮就结束。测试时优先覆盖这两个用例代码问题的排查会快很多。3.2 三种实现的时间与空间实测在 LeetCode 编辑器里分别提交三种写法我本地实测下来的数据大致是实现方式运行耗时典型内存占用典型代码行数递归28 ms16.2 MB约 10 行显式栈迭代32 ms16.5 MB约 14 行Morris40 ms15.8 MB约 22 行注意这只是 LeetCode 服务器在当前测例下的参考值不同语言和判题负载波动很大没必要为了 4 ms 的差距纠结。内存上 Morris 确实验证了 O(1) 空间但 Python 本身的解释器开销让这个差距在数值上不那么明显真正体现价值的是 C/C 这类贴近底层语言。从工程角度看我提交时首选迭代版本。原因不是递归写不对而是 LeetCode 上“递归爆栈”属于能稳定复现的悲剧类型。面试之外的应用场景里树的高度无法预先控制递归的不确定性就是风险迭代版本风险更低。3.3 三个必须跑的测试用例空树root None期望[]。很多人在本地建树时用None表示空指针提交后没注意判题器也按这个逻辑走一不留神就会在root.val上炸掉。左斜树例如[2, 1, 3, null, null, null, null]的反向用例构造一个左链足够深的树测试递归是否爆栈、迭代是否死循环。极端的链状树在 LeetCode 的判题数据里确实存在。完全二叉树例如[4, 2, 6, 1, 3, 5, 7]期望[1, 2, 3, 4, 5, 6, 7]。这个用例能顺便验证迭代代码对“左右子树都齐整”的场景处理是否正确。我习惯在本地写一个简单的build_tree辅助函数把数组转成二叉树再跑三种解法对比输出。这样提交前就能确定逻辑问题而不是靠判题器的 WA 信息去猜。4. 运行时错误高频原因与排查思路4.1 空指针90% 的二叉树报错源头写二叉树程序报运行时错误第一个排查项永远是空指针。报错信息通常是AttributeError: NoneType object has no attribute valPython 里一眼就能认出来。最典型的原因是在递归函数里没有处理node为 None 的情况就访问node.val。比如把中序写成def dfs(node): dfs(node.left) res.append(node.val) # node 为 None 时这里直接炸 dfs(node.right)这个写法连出口都没有根节点为空时第一行就崩了。正确做法是把“节点为空什么都不做”作为递归基例并且保证对任何非空节点调用递归时它的左右孩子都可以安全传入。迭代版本同理cur cur.right之前如果 cur 已经是 None下一次循环条件判断会直接退出但访问cur.val之前必须确认 cur 非空——栈 pop 出来的元素一定非空这是安全性的主要来源而内层 while 里的cur cur.left可能把 cur 改成 None此时不能碰cur.val。4.2 递归爆栈深树场景的系统性风险Python 的递归深度限制默认是 1000LeetCode 偶尔会构造深度超过这个值的测试用例表现是RecursionError: maximum recursion depth exceeded。这不是代码逻辑问题而是平台环境限制。遇到这种情况要么改用迭代版本要么手动调高递归限制sys.setrecursionlimit(1000000)但调高限制只是把阈值推迟理论上的风险依然存在。考虑到面试官通常不希望你靠调全局变量过关迭代版本才是根治方案。我踩过的一次实际例子是某道二叉树题用递归写本地测试全过提交之后若干隐藏用例疯狂报 Runtime Error。排查到最后发现是递归深度超限换成显式栈迭代之后一次 AC。之后我给自己定了条规矩二叉树题目如果心思足够直接写迭代版本省得提心吊胆。4.3 迭代死循环Morris 和指针操作的重灾区迭代版本死循环通常发生在外层循环条件判断和指针更新不配合的时候。以 Morris 为例如果恢复线索的步骤写错——例如忘记把most_right.right设回 None——第二次经过该节点时会重复建立已经存在的线索代码一直沿着左子树回溯陷入死循环。排查思路是用小样例逐步跟踪。手动模拟[1, null, 2, 3]的 Morris 过程在建立线索和恢复线索的两个分支各打印一行能快速看出 cur 是否在两个节点之间反复横跳。另一个常见死循环原因是显式栈版本的弹栈后cur cur.right写成了cur stack[-1].right混淆了“当前处理节点”和“栈顶节点”导致节点的右子树永远不会被访问但外层循环又发现栈里还有节点于是卡住。死循环在 LeetCode 上的表现是 Time Limit Exceeded不是 Runtime Error。看到超时先别急着优化常数优先怀疑是不是逻辑死循环特别是涉及指针连接的题目。4.4 常见问题速查表现象可能原因排查顺序AttributeError: NoneType object has no attribute val递归出口缺失或迭代中访问了空节点1. 检查所有访问 val 的地方 2. 确认 cur 非空 3. 检查递归基例RecursionError: maximum recursion depth exceeded递归深度超过平台限制1. 改用迭代 2. 检查是否左右子树递归分支放反Time Limit Exceeded死循环或算法复杂度退化1. 检查 Morris 线索是否恢复 2. 检查迭代 cur 更新是否正确 3. 缩小样例模拟结果顺序错误遍历逻辑顺序写反1. 检查 append 位置 2. 对照左根右语义逐层推演5. 从 Hot100 向外延伸线索二叉树与 BST 的底层联系5.1 中序遍历和线索二叉树什么关系线索二叉树的核心思路是把遍历过程中空余的指针利用起来。一棵有 n 个节点的二叉树有 n1 个空指针中序线索化就是在遍历过程中把某些空指针改造成“前驱”或“后继”的线索。Morris 遍历本质上就是在线索二叉树基础上做瞬时改造遍历完成后再把结构还原。LeetCode 题库里没有直接考线索二叉树构建的题但理解这个概念对中序迭代帮助很大。你写显式栈迭代时stack 里保存的就是“还没访问但需要回溯”的节点从语义上看就是人为记录后继关系。Morris 用空指针天然替代了这个栈只不过需要保证遍历结束后不留痕迹。如果把递归比作“系统帮你记路”迭代就是“自己记账本”Morris 则是“直接在路上做标记走完擦掉”这个类比在向别人解释时特别好用。5.2 中序遍历是二叉搜索树的万能钥匙二叉搜索树的定义决定了中序遍历输出一定递增有序。这个性质让“判断是否 BST”“找第 K 小元素”“求最小绝对差”这类题都变成了改动版的中序遍历。比如 LeetCode 98 验证二叉搜索树直观做法就是中序遍历一遍检查结果是否严格递增。虽然有更优的递归区间判断法但中序版本最容易理解和证明是新手阶段的极佳切入点。再比如 LeetCode 230中序遍历数到第 K 个节点直接返回逻辑零思考成本。这也是我在文章开头说“中序是二叉树地基”的原因。Hot100 后续的树题目里很大一部分核心操作要么是中序遍历直接出结果要么是在中序遍历基础上加状态判断。把这三种代码实现写到肌肉记忆后续的树类题会顺手很多。5.3 一句话总结三种解法的选择策略笔试时间紧首选递归最短代码拿分走人面试手写显式栈迭代展示你对函数调用栈的理解聊天环节主动提一嘴 Morris 的空间优势证明你读过教材之外的细节。三条路线不冲突关键是有意识地把三个版本都备好。6. 实操心得与建议我自己刷这道题的过程中最深的体会是把迭代版本写对之后再去理解 Morris顺畅程度远超“边学边写”。迭代版本的“一路向左压栈、弹栈访问、转向右子树”恰恰就是 Morris 在没有栈的情况下要做的事只不过 Morris 把“回溯到谁”这个信息藏在了树本身的指针里。刷题顺序上我个人建议不要急着背所有二叉树遍历的模板先把中序彻底搞懂。前序迭代是压栈时访问后序迭代可以借助“前序变体 反转”实现它们都是在中序骨架上加减一行。地基稳了三序遍历的迭代写法一晚上就能全部拿下。还有一个细节很多人觉得 Morris 空间 O(1) 很神奇就跳过迭代直接用 Morris 入门。这里我的劝阻非常明确——Morris 对边界的理解要求极高新手直接上手大概率在“建立线索”和“恢复线索”之间丢掉方向感搞不懂线索指向了哪里。先通过递归建立直觉再用迭代建立模型最后用 Morris 点亮进阶概念这条路径放在 LeetCode 任何一道树题上都适用。