我在算法训练营第13天拿到了这四道题LeetCode144二叉树前序遍历、145后序遍历、94中序遍历外加一道102层序遍历。前三个是深度优先搜索DFS的三兄弟最后一个是广度优先搜索BFS的代表题。很多同学刷到这里会觉得不就是遍历嘛递归一写就完事但实际上手才会发现真正拉开差距的是迭代写法、统一模板以及框架思维——层序遍历这一道题吃透了能直接拿下二叉树的右视图、锯齿遍历、最大深度等至少十道衍生题。这篇文章我会把四道题作为一个整体来拆解先讲清楚为什么训练营要把它们排在同一个训练日再分别从递归、迭代、BFS三个维度给出一套可以直接抄作业的代码和思路最后把我自己反复踩过的运行时错误排查经验一并分享。无论你是刚接触二叉树的新手还是刷题卡在会写但总报错阶段的进阶选手这四道题都值得你花一个晚上彻底打通。1. 四道题一把抓二叉树遍历的体系化拆解1.1 为什么把四道题放在同一天代码随想录训练营把144、145、94这三道深度优先遍历题和102这道层序遍历题放在同一天不是随机的排列组合而是刻意让你在同一天内建立DFSBFS的完整遍历观。二叉树的几乎所有题目——从求深度、找路径、判断对称到序列化反序列化——底层都离不开这四种遍历方式。按访问根节点的时机DFS遍历可以分成三类遍历方式访问顺序一句话记忆前序遍历根 - 左 - 右先处理自己再处理孩子中序遍历左 - 右 - 根先处理左孩子再处理自己后序遍历左 - 右 - 根先处理孩子最后处理自己这里有一个非常重要的规律前中后序的本质区别仅仅在于根节点被访问的时机。左孩子永远在右孩子之前被访问这个约束是固定的。前序的根左右、中序的左根右、后序的左右根实际上就是在一棵树上做三次不同顺序的打卡。理解了这一点你会发现三份递归代码长得几乎一模一样唯一不同的就是result.append(root.val)这一行放在什么位置。很多教程喜欢把三种遍历当三个独立的知识点来教我反而是强烈建议把三种遍历打印出来并列对比这样记忆效率高得多。1.2 为什么层序遍历要单独拎出来层序遍历Level Order Traversal和前中后序不同它用的是队列先进先出逐层扫描。它解决的是按层访问这个问题从上到下、从左到右把二叉树整体扫一遍。层序遍历最大的特点是可以拿到当前层的概念。这意味着我们可以知道每一层有多少个节点、某一层的平均值、某一层是否存在某个值等等。前中后序只能给你一条DFS的路径层序给你的是地图切片。这也是为什么层序遍历在生产场景中非常实用——比如渲染一棵目录树时按层级展开、计算组织架构中每一层的员工规模本质上都是层序思想。1.3 二叉树的定义与递归基在写任何遍历代码之前要先把二叉树的数据结构刻在脑子里。以LeetCode的标准定义为例# Definition for a binary tree node. class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right一个节点包含三样东西自己的值val、左子节点left、右子节点right。没有子节点时用NonePython或nullJava表示。这里有一个新手特别容易忽略的点TreeNode的left和right默认是None也就是说一个叶子节点天然拥有两个空孩子。在递归遍历时我们访问到一个空节点就直接返回这既是递归的终止条件也是后面排除运行时错误的核心。2. 递归解法最稳妥的起点2.1 递归三部曲到底在说什么递归解法的代码非常简单但很多人是背下来的并不知道每一步为什么这么写。我按照代码随想录里反复强调的递归三部曲来拆解第一步确定递归函数的参数和返回值。遍历函数preorder需要传入当前节点root同时需要一个result列表来收集结果。因为 Python 的 list 是引用传递所以我们可以把result作为参数传入在函数内部直接修改它不需要每次都返回一个新列表。第二步确定终止条件。当root为None时说明已经到了树的最底部或者空子树直接return。这是递归的出口防止无限递归导致栈溢出。第三步确定单层递归的逻辑。按前中后序的要求决定处理当前节点这一操作放在递归左子树之前、之间还是之后。很多人在刷题时会陷入一个误区觉得递归很难想明白。我的经验是——不要试图在脑子里完整展开递归调用栈只需要相信递归函数能正确处理一棵子树这一假设。就像你用print函数时不会去纠结它内部怎么把字符串输出到屏幕上一样你只需要保证单层逻辑是对的递归自然会对。2.2 三道DFS题的递归代码与对比先给出前序遍历的完整代码class Solution: def preorderTraversal(self, root: Optional[TreeNode]) - List[int]: result [] self.traverse(root, result) return result def traverse(self, root: Optional[TreeNode], result: List[int]) - None: if root is None: return result.append(root.val) # 先处理根 self.traverse(root.left, result) # 再处理左 self.traverse(root.right, result) # 最后处理右中序遍历只需要移动result.append(root.val)这一行的位置class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: result [] self.traverse(root, result) return result def traverse(self, root: Optional[TreeNode], result: List[int]) - None: if root is None: return self.traverse(root.left, result) # 先处理左 result.append(root.val) # 再处理根 self.traverse(root.right, result) # 最后处理右后序遍历同理class Solution: def postorderTraversal(self, root: Optional[TreeNode]) - List[int]: result [] self.traverse(root, result) return result def traverse(self, root: Optional[TreeNode], result: List[int]) - None: if root is None: return self.traverse(root.left, result) # 先处理左 self.traverse(root.right, result) # 再处理右 result.append(root.val) # 最后处理根这三段代码的差别就是用一行代码的位置切换了三种不同的遍历顺序。我建议你亲手把这三份代码放在同一个文件里对比着看印象会非常深刻。对新手来说递归写法是必须100%熟练掌握的因为它是后面所有进阶写法迭代、Morris遍历、回溯的基础。2.3 递归的隐藏陷阱栈溢出与系统栈递归看起来最美但也隐藏着一个大坑当二叉树退化成链表时递归深度等于节点数量。如果一棵树有10000个节点递归就会嵌套10000层。Python默认的递归深度限制大约是1000层超过之后直接抛RecursionError。这在LeetCode的测试用例里是真实存在的。处理方式有两种一是用sys.setrecursionlimit()手动调高限制但治标不治本二是改用下面要讲的迭代写法用显式的栈代替系统调用栈。如果你在测试用例上遇到RecursionError不用怀疑一定是有某个用例把退化成链表的极端情况喂进来了。这时候递归解法在理论上已经不再安全迭代写法就是你的第二方案。3. 迭代解法从模拟递归到统一模板3.1 为什么需要迭代迭代解法的本质是用一个我们自己创建的栈Stack来模拟递归过程中的调用栈。系统递归栈的大小是有限制的而自己创建的栈可以放在堆上内存更大也不会受到递归深度限制的约束。迭代解法的难点在于不同遍历顺序下节点的入栈、出栈顺序需要自己设计。这也是面试官在考察二叉树遍历时最喜欢追加的问题——你能用迭代实现吗 如果你能流畅写出迭代版本说明你是真的理解了遍历的过程而不只是会背递归。3.2 前序迭代入栈顺序是关键前序迭代有两种主流写法我先讲最直观的一种也是代码随想录里推荐的方式class Solution: def preorderTraversal(self, root: Optional[TreeNode]) - List[int]: result [] if root is None: return result stack [root] while stack: node stack.pop() result.append(node.val) # 栈是后进先出所以先压右再压左 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result这里的关键在于前序是根-左-右但栈是后进先出所以我们要先把右孩子压入栈底再把左孩子压入栈顶。这样弹出的时候左孩子会先于右孩子被访问。我经常用一摞盘子来类比你把左盘子和右盘子依次放到一摞盘子上如果你想让左盘子先被取走你就要最后放左盘子放在最上面。这个入栈顺序反直觉但写一次就记住了。3.3 中序迭代一路向左再回头中序迭代和前序完全不同。前序是每次弹出就访问的直给逻辑而中序需要一直往左走到底再回头访问。来看代码class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: result [] stack [] cur root while cur is not None or stack: # 一路向左走到底 while cur is not None: stack.append(cur) cur cur.left # 弹出栈顶节点并访问 node stack.pop() result.append(node.val) # 转向右子树 cur node.right return result这个过程可以脑补成探险家在迷宫里永远先走左岔路走到死胡同后回头看当前岔路口有没有右岔路可走有就进去继续一路向左。这里的cur node.right是最容易漏掉的一行——如果你忘了更新cur循环会永远卡在访问同一个节点上。3.4 后序迭代两个栈技巧与前序翻转后序左-右-根的迭代写法相对绕。一个非常聪明的技巧是——利用前序遍历的变体。前序是根-左-右。如果我们把前序的入栈顺序反过来——先压左再压右——那么弹出的顺序就变成根-右-左。得到这个顺序后整体 reverse 一次正好得到左-右-根的后序序列。把这两步合在一起class Solution: def postorderTraversal(self, root: Optional[TreeNode]) - List[int]: result [] if root is None: return result stack [root] while stack: node stack.pop() result.append(node.val) # 注意这里先压左再压右 if node.left: stack.append(node.left) if node.right: stack.append(node.right) # result 现在是 [根, 右, 左]反转后就是 [左, 右, 根] return result[::-1]我个人非常喜欢这个技巧因为它把后序迭代转化成了前序遍历的镜像 反转逻辑上不需要记第二种栈操作方式。另一种两栈写法也能实现但代码更长面试时容易手滑所以我更倾向于推荐反转法。3.5 统一迭代法一套模板打天下前序、中序、后序三种迭代写法的代码风格差异很大很多同学在考场上容易混淆。代码随想录里介绍了一种统一迭代法核心思想是用空指针作为访问过但尚未处理的标记。以中序为例class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: result [] if root is None: return result stack [root] while stack: node stack.pop() if node is not None: # 栈是后进先出中序左-根-右所以要按 右、根、左 的顺序压栈 if node.right: stack.append(node.right) # 右 stack.append(node) # 根 stack.append(None) # 标记根节点还没处理 if node.left: stack.append(node.left) # 左 else: node stack.pop() result.append(node.val) return result这套模板的优点是三种遍历只需要调整压栈顺序即可遍历顺序压栈顺序从底到顶前序右、左、根中序右、根、左后序根、右、左缺点是代码不够直观新手容易在None标记的处理上绕晕。我的建议是统一迭代法适合复习时梳理逻辑实际刷题时前序用最简迭代、中序用一路向左、后序用反转法反而更不容易出错。工具没有高下能让自己稳定做对的就是好工具。4. 层序遍历队列BFS的尺寸技巧4.1 BFS框架与size变量的关键作用层序遍历的代码比DFS迭代更简单核心就是队列Queuefrom collections import deque class Solution: def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]: result [] if root is None: return result queue deque([root]) while queue: # size 记录当前层的节点数量 size len(queue) level [] for _ in range(size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result这里最关键的是size len(queue)这一行它是在进入当前层循环之前记录队列的长度。为什么不能直接while queue因为循环过程中我们会不断把下一层的节点加入队列如果不先记录 size就无法区分当前层的节点和下一层的节点。打个比方你在食堂排队打饭队伍里既有正在打饭的人也有后面新来的。如果你想统计当前正在打饭的这一批人必须在开始服务前先数一下人数。size就是那个提前数好的人数。4.2 从层序遍历到十道衍生题层序遍历的框架一旦掌握以下这些LeetCode题目你只需要微调就能做出来衍生题目微调思路107. 二叉树的层序遍历 II最后把result反转199. 二叉树的右视图只收集每层最后一个节点637. 二叉树的层平均值每层求和后除以 size429. N叉树的层序遍历遍历 children 列表代替 left/right515. 每个树行中的最大值每层遍历时记录最大值116/117. 填充每个节点的下一个右侧节点指针层内遍历时连接相邻节点这六道题的核心代码骨架几乎不变改的只是对 level 列表做什么处理。训练营把102放进来目的就是让你以最小成本建立BFS框架后续遇到这些衍生题时你已经不是从零开始而是套模板微调。4.3 层序与DFS在空间复杂度上的取舍层序遍历的时间复杂度是O(n)每个节点恰好入队出队一次。空间复杂度是O(n)因为最坏情况下最后一层的节点数约等于n/2满二叉树时队列需要同时容纳它们。对比DFS递归写法的空间复杂度O(h)h是树高。平衡二叉树时hlog2(n)空间开销小得多但二叉树退化成链表时hn递归会爆栈。所以在树很深但每层节点不多的场景DFS占优在树很宽的场景BFS占优。刷题时可以根据题目要求灵活选择不必执着于某一种遍历方式。5. 运行时错误的排查经验从崩溃到全绿5.1 最常见的三类运行时错误标题相关热搜词里有一个非常扎心的说法——写二叉树程序时为什么总是报运行时错误。我在训练营这一天的提交记录里几乎把能踩的坑全踩了一遍。汇总下来最常见的运行时错误就三类第一类空指针访问。经典报错是AttributeError: NoneType object has no attribute val意思是你对一个None节点调用了.left或.val。最常见的触发场景是在递归里没有先判root is None就直接访问root.left或者迭代代码里取出了stack.pop()是None却直接访问node.val。第二类无限递归导致的栈溢出。报错是RecursionError: maximum recursion depth exceeded。原因多半是终止条件写错比如把if root is None写成了if root导致空节点无法正常返回。还有一种可能是在二叉树退化成链表时递归深度超过了系统限制。第三类列表越界/队列操作错误。用Python的list模拟队列时如果直接用pop(0)虽然能跑但时间复杂度是O(n)如果用deque却忘了popleft()要写在正确的时机可能拿到的就不是当前层的节点。数组越界在Java里更常见int[]模拟栈时top指针超出长度。5.2 防止空指针的铁律我的经验是在二叉树代码里每当你准备访问一个节点的.val、.left、.right时先问自己一句——这个节点有可能是 None 吗如果是就必须在访问前加保护。写递归时保护就写在函数第一行if root is None: return写迭代时入栈前要判空if node.left: stack.append(node.left)这一条铁律几乎能解决90%的运行时错误。LeetCode的测试用例设计非常刁钻空树、只有左子树的树、只有右子树的树都会喂进来。你只要有一次漏判就会在某个用例上原地爆炸。5.3 用最小样例验证逻辑每次写完代码不要急着点提交先用一个最小样例在脑子里过一遍。我会固定用这棵树来做测试1 / \ 2 3 / \ 4 5前序遍历期望结果[1, 2, 4, 5, 3]中序遍历期望结果[4, 2, 5, 1, 3]后序遍历期望结果[4, 5, 2, 3, 1]层序遍历期望结果[[1], [2, 3], [4, 5]]这四个期望结果建议直接背下来。每次写完遍历代码在本地或者脑子里用这棵树跑一遍如果结果对不上基本可以锁定是访问顺序或入栈顺序出了问题。5.4 排查技巧打印法与分治排查如果代码逻辑复杂直接用print调试比干瞪眼快得多。我常用的方式是打印访问过程stack [root] while stack: node stack.pop() print(f弹出节点: {node.val if node else None})打印结果能直观地看出出栈顺序是否符合预期。还有一种方法是分治排查如果你不确定是压栈顺序错了还是终止条件错了就先把终止条件极端化——比如只处理一个节点的树看代码能不能正确输出[1]。能输出说明基本框架对再把树扩展到两层逐步定位。我个人实际刷题时最喜欢的一句话是运行时错误不可怕可怕的是不看报错信息盲目改代码。Python报错会明确告诉你发生在第几行沿着行号往上找先是A处访问了None属性顺着这个线索再往上找是因为B处把None压进了栈基本两轮就能定位根因。5.5 这四道题之后的复习建议第13天结束之后我建议你花一天时间做一次遍历专题复盘把四道题的递归、迭代、统一迭代各写一遍然后试着不看代码直接写层序遍历。如果你能做到15分钟内把四道题全部AC说明这一关已经过了。接下来再往后刷二叉树的其他题目时你会发现一个特别有意思的现象判断一棵树是否对称、求二叉树最大深度、找树左下角的值……这些题的本质都是遍历的变形。你并不需要学新东西你需要的是把遍历的框架刻进肌肉记忆。从代码随想录训练营的节奏来看第13天只是二叉树专题的起点但恰恰是这最基础的四种遍历方式决定了你之后刷二叉树题目的上限。今天把递归和迭代彻底打通后面每道二叉树的题目你都会走得比其他人稳。