代码随想录训练营进入第十三天终于轮到二叉树了。这一天安排的LeetCode 144、145、94三道深度优先遍历加上102层序遍历四道题放在一起其实很有讲究——它们就是二叉树最核心的遍历框架后续所有跟树相关的题目十有八九都要在这套框架上做文章。不管你是准备面试、刷LeetCode热门100题还是单纯想把递归思想吃透这四道题都是绕不过去的基石。这篇文章我不打算把官方题解复述一遍而是按我实际刷题时的思路讲清楚每道题在考什么、递归和迭代怎么选、层序模板怎么背以及那些经常让人报运行时错误的坑到底出在哪里。1. 内容整体设计与思路拆解1.1 为什么训练营把四道题放在同一天先说时间线。代码随想录训练营前几天的内容基本是数组、链表、哈希表、字符串这些线性结构到了第十三天突然切入二叉树本质上是换了一套思维模式从一个一个处理变成一层一层处理。LeetCode 144、145、94分别是前序、后序、中序遍历它们都属于深度优先搜索DFS102层序遍历则是广度优先搜索BFS。训练营把它们放在同一天目的很明确让你用同一棵二叉树把递归怎么写栈怎么写队列怎么写一次性对比明白。前中后序是一组它们只是访问根的时机不同层序是另一组它要求你掌握队列的按层控制。我之前见过不少朋友刷题时东一题西一题今天做做最大深度明天做做路径总和结果每种题都要重新看一遍题解。其实这些题全部建立在遍历顺序之上。第十三天的价值就在于用四道题撬动整个二叉树题单先把遍历框架焊死在脑子里后面遇到复杂题目才知道改哪里。1.2 前中后序的本质根节点在什么时机被处理很多人把前中后序背成根左右左根右左右根但真到了写代码的时候还是会卡住。我的经验是不要死记顺序要理解递归过程中每个节点被经过三次。你可以把递归遍历想象成走迷宫时在墙上画线第一次经过节点时处理它就是前序第二次回到节点时处理它就是中序第三次离开节点时处理它就是后序。所以同一段递归代码只要把处理逻辑放在左子树递归调用之前、之间还是之后就对应三种遍历顺序。这也是为什么代码随想录反复强调统一递归模板——你只需要动一行代码的位置。理解了这一点你会发现前中后序遍历根本不是三套知识是一套知识换了三次位置。1.3 层序遍历为什么单独拿出来BFS模板前中后序每次递归往深处走层序却是一层一层横向扫。LeetCode 102要求返回的是ListListInteger每一层单独一个List这个数据结构暗示了层序的核心难点怎么知道当前元素属于哪一层标准解法是队列加固定size循环。每次进入while循环时queue.size()就是当前层的节点数先把这个size存下来然后严格处理size个节点处理完这一批队列里剩下的正好是下一层节点。这个过程很像食堂打饭窗口每次放固定人数进去数完人数再放下一批这样每一批人不会混在一起。2. 递归实现与统一思路2.1 递归三要素与三序遍历的一行之差递归写法首先要理清三件事参数和返回值、终止条件、单层递归逻辑。参数这四题都需要一个集合来存结果所以一般定义一个辅助函数traversal(TreeNode cur, ListInteger result)终止条件cur null直接返回这是递归的自然出口单层逻辑按顺序做三件事——处理当前节点、递归左子树、递归右子树。以Java为例前序递归代码如下class Solution { public ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); traversal(root, result); return result; } private void traversal(TreeNode cur, ListInteger result) { if (cur null) { return; } result.add(cur.val); // 中第一次经过时处理 traversal(cur.left, result); // 左 traversal(cur.right, result); // 右 } }中序就是把result.add(cur.val)移到左子树递归之后、右子树递归之前traversal(cur.left, result); result.add(cur.val); traversal(cur.right, result);后序就是放在两次递归之后traversal(cur.left, result); traversal(cur.right, result); result.add(cur.val);你看三份代码结构一模一样只有处理当前节点的位置在变。这就是前面说的一行之差。我建议第一次刷的时候直接在自己本子上把这三个版本并排写出来对比着看比孤立地刷三遍有效得多。2.2 迭代实现显式栈模拟系统调用栈递归虽然简洁但面试时经常被要求写迭代版原因很现实递归调用依赖系统栈一旦树的深度过大可能栈溢出迭代版用显式栈空间可控也更贴近工程实现。前序迭代是三个里面最直观的。根先入栈弹出后先压右孩子再压左孩子因为栈是后进先出左孩子会后压但先弹出出栈顺序正好是中左右class Solution { public ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); result.add(node.val); if (node.right ! null) { stack.push(node.right); } if (node.left ! null) { stack.push(node.left); } } return result; } }中序迭代就不一样了。前序是遇到根就处理中序要求先处理完左子树再处理根所以必须先把左边界一路压入栈中。移动指针cur从根开始一路cur cur.left同时入栈直到cur为空弹出栈顶这时弹出的节点就是当前最左节点处理它然后转向右子树class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); result.add(cur.val); cur cur.right; } return result; } }这个版本里最容易写错的是最后一行cur cur.right。很多人忘记更新指针导致while循环永远处理同一个节点然后死循环、超时。记住弹出并处理完一个节点后下一步必须去探索它的右子树即使右子树为空也要把cur置空否则会重复入栈。后序迭代有个偷懒但很稳的技巧前序是根左右后序是左右根。如果先做根右左再把结果反转就是左右根。实现上只要把前序迭代里右孩子先入栈改成左孩子先入栈然后整组结果Collections.reverse(result)class Solution { public ListInteger postorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); result.add(node.val); if (node.left ! null) { stack.push(node.left); } if (node.right ! null) { stack.push(node.right); } } Collections.reverse(result); return result; } }这个反转法不需要硬记后序的入栈顺序面试时不容易翻车。不过要明白它只是取巧真正的后序迭代是每个节点要等左右子树都处理完才输出用反转法绕过了这个难点逻辑上没问题但面试官如果深问你还是要能说出本质区别。2.3 统一写法的标记法一套模板吃三种遍历前中后序的迭代写法各不相同有朋友觉得记不住。代码随想录里也提过一种统一写法思路是用一个空节点null作为标记。当一个普通节点弹出后不立刻处理而是把它和它的左右子树按期望处理顺序的逆序压回栈并在需要延迟输出的节点上方压一个null标记当弹出null时下一个弹出的节点才真正输出。中序统一模板class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); if (root ! null) { stack.push(root); } while (!stack.isEmpty()) { TreeNode node stack.pop(); if (node ! null) { if (node.right ! null) { stack.push(node.right); } stack.push(node); stack.push(null); if (node.left ! null) { stack.push(node.left); } } else { result.add(stack.pop().val); } } return result; } }前序和后序就是调整压栈顺序。前序需要中左右那压栈逆序就是右左中但中要延迟输出所以压入顺序是右、左、中、null后序需要左右中压入顺序是中、null、右、左。这个方法更像是把递归逻辑用栈显式表达理解了以后不用背三个版本。不过我的个人建议是日常刷题用前序迭代中序迭代后序反转法足够统一标记法适合你想深入理解栈行为时再用不要因为这个模板看起来统一就硬套反而忽略了每种遍历本身的特点。3. 层序BFS完整实现与细节3.1 层序遍历模板与代码LeetCode 102的层序遍历核心是队列。Java里用LinkedList实现Queue接口offer入队、poll出队。每层开始时先记录int size queue.size();然后用for循环精确处理size个节点这个size千万不能直接写成queue.size()因为循环过程中队列长度一直在变。class Solution { public ListListInteger levelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int size queue.size(); ListInteger level new ArrayList(); for (int i 0; i size; i) { TreeNode node queue.poll(); level.add(node.val); if (node.left ! null) { queue.offer(node.left); } if (node.right ! null) { queue.offer(node.right); } } result.add(level); } return result; } }很多新手第一次写层序容易在for循环里直接queue.size()结果每一层只处理了部分节点输出结果全错。记住这个口诀层数由while控制层内个数由size定格。3.2 复杂度分析与边界条件层序的时间复杂度是O(n)每个节点恰好入队出队一次。空间复杂度取决于队列中最多同时存在的节点数最坏情况是最后一层近似n/2个节点所以也是O(n)。边界条件主要有两个空树root null时返回new ArrayList()不要返回null。LeetCode期望空树返回空列表[]不是null这地方我踩过坑单节点树根节点只有自己处理好size1的循环后result里就是[[root.val]]。如果想验证自己写的层序对不对我常用的办法是把结果按层打印出来比如[[3],[9,20],[15,7]]直观看到每层的分界。LeetCode上很多二叉树的题都可以基于这个模板改比如二叉树的右视图、每层最大值、N叉树层序遍历都是在固定模板里加一点逻辑而已。4. 常见问题与排查技巧实录4.1 写二叉树程序时为什么总是报运行时错误最近很多刷题群都在问写二叉树程序时为什么总是报运行时错误我排查过不少基本都是下面几类一个个说。第一类空指针异常。最常见。比如递归处理某个节点时没有判断cur null就直接访问cur.left或者层序中queue.poll()返回null然后直接调node.left。LeetCode的测试用例特别喜欢给空树、只有单边子树的极端场景建议在入口处就先判空递归版判断当前节点是否为空迭代版判断根是否为空。第二类栈溢出。二叉树递归深度等于树高。如果一棵树是链状的节点数一万个递归版基本就StackOverflowError了。LeetCode有些评测数据比较极端递归不是不能用但要心里有数。遇到大深度场景迭代版更稳。第三类死循环导致Time Limit Exceeded。中序迭代里cur没有正确更新或者层序里忘了poll()都会造成死循环。排查方法很简单在自己编辑器里加一个计数器超过节点总数就打印信息十有八九是哪个分支没有前进。第四类集合返回值不对。题目要求ListListInteger你返回成ListInteger编译都过不了。还有一类是每层复用同一个List没有在每次循环里new ArrayList()最后结果里全是最后一层的重复内容。第五类空树返回问题。递归前序如果root null直接返回result是空列表没问题但如果入口写了result.add(root.val)再判断空树就炸了。先判空再处理顺序别反。4.2 LeetCode 提交答案的格式坑二叉树相关题目的输入输出都比较特殊提交前要确认三点。一是TreeNode结构。LeetCode已经在后台定义好了你不用自己写但本地调试时需要自己定义一个TreeNode类包含val、left、right字段和构造方法否则本地跑不起来。二是返回值类型。前中后序遍历返回ListInteger层序返回ListListInteger。Java里初始化要这样写ListInteger result new ArrayList(); ListListInteger result new ArrayList();第一行左边是接口右边是具体实现这是Java集合的基本习惯但新手经常写成ListInteger result new List();编译直接报错因为List是接口不能实例化。三是空值策略。部分题目对空树的返回值定义很严格比如层序返回空列表而不是null你要严格按照题目的示例来不要凭感觉。4.3 训练营刷题节奏与复习建议代码随想录训练营第十三天安排这四道题本质是让你建立二叉树遍历的肌肉记忆。我的建议是当天不要只把四道题各刷一遍就完事至少手写一遍遍历序列。具体复习节奏可以这样随便画一棵树手动写出它的前、中、后、层序序列再跑一遍代码对比第二天把四道题重新做一遍不看题解检验是否真的记住模板后面遇到二叉树相关题目先问自己这题需要DFS还是BFS如果是DFS用前中后哪个序这套流程看起来笨但效果很好。很多LeetCode热门100题比如二叉树的最大深度、二叉树的最近公共祖先、路径总和本质上都是遍历框架里加一点判断或计算。遍历序没学扎实后面每道题都要重新受苦。5. 从四道题延伸出去的面试体系5.1 这几道题可以直接套的变种题一旦四道题的模板熟了很多题就是改一行的事。我列几个典型的方便你验证自己是否真正掌握。二叉树的最大深度后序遍历或层序每下一层深度加一层序可以直接数while循环次数二叉树的最小深度层序找到第一个没有左右孩子的节点立即返回当前层数N叉树的层序遍历把node.left/right换成遍历node.children列表二叉树的右视图层序遍历每次只取每层最后一个节点二叉树的锯齿形遍历层序遍历加上一个反转标记偶数层结果逆序。这些题我刷的时候都是直接复制层序模板再改局部几乎没有额外学习成本。这就是第十三天的四道题带来的复用价值。5.2 进阶Morris遍历的O(1)空间思路如果面试官追问能不能不用栈也不用递归O(1)空间遍历二叉树就轮到Morris遍历了。它的核心是利用叶子节点大量空闲的左右指针把节点串成线索实现遍历后还能恢复原结构。虽然LeetCode这四道题用Morris有点杀鸡用牛刀但理解它能帮你更深刻地认识二叉树的结构。具体说Morris中序的大致步骤是从根开始如果左子树为空直接访问当前节点并转向右子树如果左子树不为空找到左子树的最右节点把它右指针指向当前节点建立线索然后当前节点移向左子树当再次经过这个最右节点时说明左子树已经遍历完恢复它的右指针为空同时访问当前节点并转向右子树。空间确实压到了O(1)但代码比较复杂我建议面试时先提递归或迭代Morris作为加分项了解即可。5.3 我的几点实操心得最后说几个我自己刷这四道题攒下来的经验不是标准答案但很顶用。第一写前中后序迭代之前一定先把递归版写顺。我见过太多人直接背迭代代码背完三周就忘。递归版一旦通了迭代版是为什么这么写的答案不是另一套死活记不住的东西。第二Deque优于Stack。Java老版本里Stack继承自Vector有同步开销而且性能差现代写法都是用ArrayDeque当栈用。虽然LeetCode上用Stack也能过但工程习惯要从刷题时就开始养成。第三层序模板里的int size queue.size();是这四道题里最值得记住的一行。后面做图、多叉树、状态BFS这个先定格再扩散的思路会陪你走很远。第四遇到运行报错先不急着看题解把测试用例画出来手推一遍再单步调试。LeetCode最常见的空指针和死循环几乎都是因为脑子里没有树的样子代码和结构对不上。耐心画几次图二叉树这块才算真的进脑子了。