1. 先把“中序”这两个字吃透左、根、右到底是怎么走的LeetCode 热题 100 第 36 题力扣原题 94要求返回二叉树的中序遍历。题目描述的返回值很简单但递归和迭代两种实现方式直接区分了“背过模板”和“真的理解遍历是怎么发生的”这两类人。中序遍历的顺序是先遍历左子树再访问根节点最后遍历右子树。别看这句口诀只有九个字它最容易被误读的地方是“左子树”而不是“左节点”。举个例子经典的测试用例数组是[1, null, 2, 3]很多新手一看就觉得输出应该是[1, 2, 3]但正确答案是[1, 3, 2]。为什么会这样因为数组是二叉树的层序序列不是中序序列。它还原出来的树长这样1 \ 2 / 3这里 3 是节点 2 的左孩子。中序遍历从根节点 1 开始1 没有左子树所以先访问 1然后进入右子树右子树的根是 2。2 有左孩子 3所以必须先处理 3最后才轮到 2。整个顺序就是 1、3、2。这个例子告诉我们两件事第一中序的“左根右”是递归定义访问到任何一个节点时都要先完整处理它左子树内部的先后关系然后再处理这个节点自己。第二理解遍历顺序最好的方式是画一棵小树亲手把递归展开一遍而不是背输出的顺序。靠记忆顺序做题遇到稍微复杂一点点的树就会翻车。还有一个很多人忽略的点中序遍历对二叉搜索树特别重要。二叉搜索树的中序遍历结果是有序的所以这道题也常常作为验证二叉搜索树、求第 K 小元素等题目的前置知识。也就是说这一题不是单独存在的它是后面很多树的题的地基。2. 递归解法三行核心逻辑递归栈替你扛了所有细节递归解法几乎是中序定义的直接翻译。题目要求返回一个 List那就用一个外部数组res承接结果再定义一个内部递归函数dfs去遍历。代码如下from typing import Optional, List class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] def dfs(node: Optional[TreeNode]) - None: if node is None: return dfs(node.left) res.append(node.val) dfs(node.right) dfs(root) return res这个写法有三个关键点值得展开说。第一个是终止条件。if node is None: return不能省也不能简单换成if not node.left and not node.right。因为空节点不只是叶子节点的孩子还可能是整棵空树的根。比如root本身就是None时没有这个判断立刻就会报“NoneType”相关错误。换一种说法每一次递归进入函数时你的参数可能就是个空引用必须先把这一层挡住。第二个是递归顺序。dfs(node.left)会一直往左走直到走到空节点然后回溯一层执行res.append(node.val)再进入dfs(node.right)。如果画一个调用栈你会看到栈顶永远是最左边还没处理完的节点。左子树全部结束之后函数才会回到上一层处理上一层节点的append。这和中序定义的“左、根、右”完全一致。第三个是关于结果数组的传递。我见过有人这样写return dfs(node.left) [node.val] dfs(node.right)功能上没错但每次递归都产生新列表时间和空间都会变成 O(n²)。用外部res在递归过程中持续append才是 LeetCode 上最稳妥、也最容易理解的写法。这个“共享结果容器”的思路在后续很多树的题目里都会用到比如路径总和、层序收集结果等。递归解法的时间复杂度是 O(n)因为每个节点恰好访问一次。空间复杂度是 O(h)h 是树的高度递归栈最深会压到树的高度。最坏情况下树退化成一条链h 等于 n此时递归深度可能很大。LeetCode 的测试用例里一般不会出现极端的十万级链式树但在本地调试时遇到过RecursionError的朋友应该深有体会。面试里先给递归解再被追问“能不能不用递归”就进入下一节的内容了。3. 迭代解法用显式栈把递归过程演出来面试官就爱看这个递归方案虽然简洁但面试官通常会追问一句你能用迭代写吗所谓迭代本质是自己维护一个栈复现递归时系统隐式维护的调用栈。但注意不需要把每个递归栈帧完整模拟出来只要保证访问顺序仍然是“左、根、右”即可。标准写法如下class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] stack [] cur root while cur is not None or stack: while cur is not None: stack.append(cur) cur cur.left cur stack.pop() res.append(cur.val) cur cur.right return res这个代码的核心逻辑可以拆成两个阶段看。第一个阶段是内层while从当前节点出发一路把沿途节点压入栈同时把cur指向左孩子直到左孩子为空。第二个阶段是外层循环弹出栈顶节点把它的值加入结果然后把cur指向它的右孩子。右孩子如果是空下一轮外层循环会继续弹栈右孩子不为空就又会进入内层循环去压右子树左侧的那条链。这里最反直觉的一点是为什么一开始要“一路向左压栈”而不是直接把根先访问了因为中序要求左子树先访问。可你走到根节点的时候它的左子树还没看当然不能急着输出。于是就得先把根存在栈里把左边一路走完。等左边走到底了再逐个弹出弹出的过程就是在“补记”之前存下来的节点。弹出之后又转向右子树相当于把右子树当作一棵全新的树继续执行同样的流程。用前面那棵树[1, null, 2, 3]手动推一遍你会看得更清楚步骤当前操作cur 指向stack栈底→栈顶res1初始状态1[][]21 入栈cur 指向 1.leftNone[1][]3弹出 1访问 1cur 指向 1.right2[][1]42 入栈cur 指向 2.left3[2][1]53 入栈cur 指向 3.leftNone[2, 3][1]6弹出 3访问 3cur 指向 3.rightNone[2][1, 3]7弹出 2访问 2cur 指向 2.rightNone[][1, 3, 2]循环结束。可以看到每个节点只入栈一次、出栈一次时间复杂度稳定在 O(n)。栈的最大深度取决于树高最坏情况 O(n)所以空间复杂度同样是 O(h)。从复杂度上看迭代和递归没有本质差别但迭代不依赖系统递归栈也不会触发递归深度限制在实际工程里更可控。这段代码建议自己默写三遍。不是死记而是边写边想内层循环压的是什么外层循环弹出来的节点为什么可以直接访问弹出来之后为什么必须让cur cur.right这三个问题想通了中序迭代就算真正掌握了。4. 迭代解法的三个易错点空指针、死循环、顺序错乱LeetCode 的树类题目里最常见的一类报错就是运行时错误而中序迭代恰好是“空指针”和“无限循环”的高发区。我总结了自己和身边朋友踩过最多的三个坑每一个都能对到具体的症状上。4.1 最常见的 Runtime Error在 None 上访问属性报错通常是这样的AttributeError: NoneType object has no attribute val原因很简单你的代码拿了一个None当作TreeNode去访问属性。比如递归解法里少了if node is None: return或者迭代解法里用while stack:但初始cur是None然后在内层循环直接操作cur.left。再比如有人会把None塞进栈里弹出来之后执行cur.val一样炸。避免方法只有一条任何访问节点属性之前先确认它不是空引用。递归版本用终止条件挡迭代版本用while cur is not None or stack保证内层循环不会在空节点上继续操作。调试时如果报了错不要只盯着报错行往上跑一层看看是哪一步把一个空值带到了这里。4.2 死循环和漏遍历问题多半出在“右子树”没接上这是另一种经典场景代码运行完结果只输出了左半部分或者干脆卡住超时。我见过最典型的错误写法是弹出节点并访问后忘记写cur cur.right。少了这一行会怎样假设弹出节点 1 并访问后cur仍然指向 1。下一轮外层循环进来内层循环又把 1 压回栈然后继续往左走。如果 1 的左孩子为空马上又弹出 1又访问一次。于是 1 被重复访问右子树永远轮不到甚至可能形成死循环。所以cur cur.right这行不是可有可无它决定了整个流程能不能从“左子树阶段”切换到“右子树阶段”。另一个常见问题是循环条件写成了while cur is not None:漏了or stack。比如一棵根节点为 1、左孩子为 2、右孩子为 3 的树代码先把 1 和 2 压栈2 弹完后cur变成空但此时栈里还有 1循环却直接结束了。最终结果少了根节点 1 和右子树 3输出变成[2]。这就是典型的漏遍历。排查这类问题有两个技巧。第一准备一棵极小的树比如[1, 2, 3]它期望的输出是[2, 1, 3]。如果结果不是这个顺序说明某个基本环节错了不要拿复杂用例调试。第二在关键位置加上打印把cur、stack、res的状态打出来print(cur:, cur.val if cur else None, stack:, [node.val for node in stack], res:, res)运行一次后立刻能看出是哪个节点被提前访问了还是哪个分支根本没进去。这个打印习惯对后续所有树的题都适用。4.3 顺序错乱根节点被提前访问了还有一种隐蔽的错误是结果顺序不对。比如树是[1, 2, 3]期望是[2, 1, 3]却输出了[1, 2, 3]。这种通常是因为第一轮循环就访问了根而不是先把左子树压栈。有人可能会下意识地想栈是先进后出先把根放进去再把左节点放进去弹出时不就是先弹左节点吗逻辑听起来对但中序不是单纯“先压谁”的问题而是必须保证“根节点左子树全部结束后才访问根”。如果代码在压栈后立刻访问根就等价于先访问父节点再访问左子树变成了前序遍历。所以判断顺序是否正确最直接的方法就是看那棵只有三个节点的小树[1, 2, 3]中序一定是左、根、右也就是2, 1, 3。只要输出顺序不对十有八九是“根访问得太早”。5. 从这题延伸统一迭代模板、Morris 遍历以及怎么刷更稳中序遍历既然能用迭代写前序和后序自然也能。如果你不想为三种遍历各记一套完全不同的迭代代码可以用一个统一模板——标记法也叫“颜色标记法”。它的思路是栈里存(node, visited)二元组visited为False表示节点第一次见到还没有访问过visited为True表示这个节点已经可以输出了。中序的标记法代码如下class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] stack [(root, False)] while stack: node, visited stack.pop() if node is None: continue if visited: res.append(node.val) else: stack.append((node.right, False)) stack.append((node, True)) stack.append((node.left, False)) return res因为栈是后进先出这段代码压入顺序是“右、根、左”弹出顺序就是“左、根、右”天然满足中序。想改成前序就调整压入顺序为“右、左、根标记 True”想改成后序就调整压入顺序为“根标记 True、右、左”。这个模板虽然比标准迭代多存了一个布尔值运行效率略低一点但思路统一不需要为每种遍历单独推导适合在面试现场快速给出正确答案后再优化。除了标记法还有一个进阶方案叫 Morris 遍历。它的核心是借用叶节点的空闲指针把当前节点左子树中最右的节点临时指向当前节点这样遍历完左子树后能顺着这个临时指针回到当前节点从而省掉栈。空间复杂度能从 O(h) 降到 O(1)。代码大概是这样的class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] cur root while cur is not None: if cur.left is None: res.append(cur.val) cur cur.right else: pre cur.left while pre.right is not None and pre.right ! cur: pre pre.right if pre.right is None: pre.right cur cur cur.left else: pre.right None res.append(cur.val) cur cur.right return res这段话可能第一次看有点绕但它的本质就是“线索二叉树”的思路利用空闲右指针建立临时线索完成回溯。Morris 遍历在面试中是加分项不是这一题的必须项。第一遍刷题先把递归和标准迭代吃透第二遍再回头啃 Morris 会顺畅很多。最后说说我自己的刷题体会。真正让我对中序迭代开窍的不是背模板而是把“递归栈”翻译成“待办清单”去理解当你在某个节点时你先把右子树、自己、左子树这三件事按“后进先出”的顺序塞进清单然后一直处理清单顶端的事项。中序的特殊之处就是“自己”这件事必须排在左子树之后。想通这一点后前序、后序、层序甚至更复杂的树形 DFS你都能从顺序推导出代码而不是死记每一步该压什么。这道题值得多刷几遍每刷一遍都会对“遍历”这两个字有更清楚的认识。