代码随想录算法训练营走到 DAY14第六章二叉树 part02正好是我觉得二叉树整个板块里性价比最高的一组题。原因很简单这里的主线是层序遍历一个模板能串起至少七八道 LeetCode 题同时最大深度、最小深度这两个高频考点也会在这一天集中出现。如果你已经跟着训练营刷到第六章前面递归遍历、迭代遍历的底子还在那么 DAY14 就是你从“会遍历二叉树”切换到“会用遍历解题”的转折点。这篇文章不打算把每道题的题解重新抄一遍而是想从“为什么这样安排”“模板要背到什么程度”“哪些坑我踩过”三个角度把二叉树 part02 整理成一份能直接消化吸收的笔记。适合正在打卡训练营、以及准备算法面试但一直在树型递归里绕弯的同学。1. 层序遍历模板这组题里最该先“背下来”的套路1.1 深度优先与广度优先在树上完全是两种心流前几天的训练营里我们刚把二叉树的前中后序遍历过了一遍递归法、迭代法、统一迭代法每版代码都在跟栈打交道。part02 突然换到层序遍历有些人第一反应是“又来一套新模板”心里有点抵触。但我的真实感受是层序这套东西比前中后序的迭代法好理解太多了因为它就是从“按层扫描”的直觉出发的。深度优先遍历是“一条路走到黑”从根出发先钻到最左的叶子再一层层回溯。广度优先遍历则是“一圈一圈往外扩”先处理根再处理根的所有子节点然后处理这些子节点自己的子节点。放到树上前者天然对应栈后者天然对应队列。树中没有环所以 BFS 连 visited 数组都能省掉只要按层切分队列即可。我在训练营群里见过有人问层序遍历为什么一定要用队列用 vector 加一个下标指针行不行其实也行——用一个 vector 模拟队列不断追加子节点再用一个变量记录当前处理到哪个下标。但从代码可读性、统一性上讲queue 是最贴近“广度优先”直觉的写法。而且这个队列 BFS 的套路后面学图论、拓扑排序时还会复用现在多写几遍不亏。1.2 模板本身不长关键是“分层”这个动作层序遍历的标准模板几乎所有刷题人都见过vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (root nullptr) return result; queueTreeNode* que; que.push(root); while (!que.empty()) { int size que.size(); vectorint level; for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); level.push_back(node-val); if (node-left) que.push(node-left); if (node-right) que.push(node-right); } result.push_back(level); } return result; }这段代码看起来平淡无奇但里面藏着一个所有新人都容易踩的坑for 循环的条件不能直接写成i que.size()。原因很简单这一层遍历的过程中你不断把子节点 push 进队列que.size() 一直在变大。如果不先把 size 存下来原本只该处理 3 个节点的一层很可能变成处理 6 个、9 个最后把下一层的节点也塞进了当前层的数组里。我第一次写层序时就在这里翻过车。当时的代码逻辑整体方向是对的输出的嵌套层级却完全错乱调了很久才发现是 for 循环的边界条件问题。那之后我就养成了一个习惯凡是从队列里按“层”取数据第一步永远先把que.size()存成变量这是层序遍历模板的命根子。1.3 模板背到什么程度算合格我给自己的标准是打开一个空白文件两分钟内能默写出完整的 levelOrder并且能现场解释队列里任意时刻存着哪些节点。为什么要求这么高因为后面所有变体题都建立在“我能秒写模板”的前提上。如果你连模板都要现场想半天那变体题根本没时间改。默写不是让你死记硬背而是要形成肌肉记忆把脑力留给“这题要改哪里”的思考上。2. 八个变体题怎么改模板一次学会等于握住同类题的密码2.1 一张表厘清全部变体DAY14 这组题目看似一道接一道实际上全是同一个模板的微调。我把常见变体整理成了一个表刷题前先看一遍心里就有底了题目对模板的改动解题本质102. 二叉树的层序遍历不用改原模板107. 二叉树的层序遍历 II最后 reverse(result)方向反转199. 二叉树的右视图if (i size - 1)才收集节点取每层最后一个637. 二叉树的层平均值每层求和再除以 size层内聚合515. 在每个树行中找最大值每层维护一个 max层内聚合429. N 叉树的层序遍历遍历 children 数组孩子数量从 2 变 N116/117. 填充每个节点的下一个右侧节点指针用 pre 指针把每层串起来层内串联104/111. 最大/最小深度depth 计数111 遇叶子提前返回层数统计这张表的价值在于它帮你把“刷题”变成了“改模板”。看到 199 右视图你不需要重新设计算法只需要问自己右视图和层序遍历差在哪差在每层只要最右边的节点而最右边的节点在层序里就是i size - 1的那一个。2.2 层内聚合637 平均值与 515 最大值这两题放到一起说因为它们连代码结构都几乎一样。637 层平均值只要在每层循环里维护一个 sumfor (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); sum node-val; if (node-left) que.push(node-left); if (node-right) que.push(node-right); } result.push_back(sum / size);515 每行最大值同理把 sum 换成 max 变量int maxVal INT_MIN; for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); maxVal max(maxVal, node-val); // push children... } result.push_back(maxVal);这类题的共同点是层序遍历天然保证“同一层的节点在同一批被处理”所以任何“按层统计”的需求都只是在 for 循环内部加个变量而已。你不需要关心子树到底有多深只需要相信队列已经把该分组的分好了。2.3 107 自底向上一个 reverse 背后的理解107 的题意是自底向上层序遍历比如最后一层在最前。最直接的做法是在层序模板跑完后把 result 反转reverse(result.begin(), result.end());很多题解喜欢用insert(result.begin(), ...)来避免最后 reverse我建议不要这么做。原因有两条第一insert每次插入都会引起 vector 元素整体搬移数据量大时效率不如统一 reverse第二面试时“先层序再反转”的思路最清晰你和面试官沟通成本最低。算法题最重要的不是展示花活是让对方快速理解你的解法。2.4 429 N 叉树的层序遍历唯一结构变化N 叉树的节点定义不是 left/right而是一个 children 数组vectorvectorint levelOrder(Node* root) { vectorvectorint result; if (root nullptr) return result; queueNode* que; que.push(root); while (!que.empty()) { int size que.size(); vectorint level; for (int i 0; i size; i) { Node* node que.front(); que.pop(); level.push_back(node-val); for (Node* child : node-children) { if (child) que.push(child); } } result.push_back(level); } return result; }二进制树每个节点最多两个子节点N叉树就是把这个“最多两个”扩展成“任意多个”。只要理解 left/right 只是子节点的特例这题就毫无难度。我在训练营打卡时见过不少同学在这题卡住其实是因为一直在背二叉树模板没有停下来想想“左孩子右孩子”本质是怎么回事。3. 最大深度和最小深度的“递归双胞胎陷阱”3.1 104 最大深度为什么答案是 max 不是 min二叉树的最大深度力扣 104看起来太简单了简单到很多人直接背答案int maxDepth(TreeNode* root) { if (root nullptr) return 0; return 1 max(maxDepth(root-left), maxDepth(root-right)); }这段代码为什么用 max 不用 min因为树的深度由更深的那一侧决定。一棵树左子树有 3 层右子树是空的整棵树的深度是 4而不是 1。空子树返回 0 是对的但不能把 0 当成“有效深度”去参与最小值比较。我还见过一个误区有人觉得递归太慢非要写层序版。其实对 104 来说递归版简洁到不需要优化层序版反而显得绕。但作为训练营打卡两种写法最好都会因为后面的题目有些用递归好写有些用迭代好写提前都见一遍遇到新题时才有备选方案。3.2 111 最小深度直接套 min 会出大问题这才是 DAY14 真正值得多花时间的题。很多人看完最大深度会想当然写出“对称版”最小深度// 错误示例 int minDepth(TreeNode* root) { if (root nullptr) return 0; return 1 min(minDepth(root-left), minDepth(root-right)); }这段代码在大多数测试用例下都能挂掉。核心原因最小深度的定义是“从根节点到最近叶子节点的最短路径上的节点数”叶子节点是左右孩子都为空的节点。如果一棵树只有一个孩子比如 root 只有左子树那最小深度应该是 2——根到节点 2 的路径上有两个节点而节点 2 就是叶子。但错误模板会算出 1。因为它把右子树为空的 0 当成了一个合法深度min(1, 0) 选了 0最后返回 1。而 root 本身左右孩子并不全空它不是叶子深度 1 是错的。正确写法的核心是处理“单边为空”的情况int minDepth(TreeNode* root) { if (root nullptr) return 0; if (root-left nullptr root-right nullptr) return 1; if (root-left nullptr) return 1 minDepth(root-right); if (root-right nullptr) return 1 minDepth(root-left); return 1 min(minDepth(root-left), minDepth(root-right)); }这种写法把边界条件全摊开了一开始可能觉得啰嗦但它能帮你彻底避开“空节点冒充叶子”的坑。如果你喜欢更紧凑的写法也可以这样int minDepth(TreeNode* root) { if (root nullptr) return 0; int left root-left ? minDepth(root-left) : INT_MAX; int right root-right ? minDepth(root-right) : INT_MAX; if (left INT_MAX right INT_MAX) return 1; return 1 min(left, right); }用 INT_MAX 表示“这一侧不存在”这样就不会让空分支的 0 参与最小值比较。可读性稍差一点但逻辑更紧凑。3.3 层序碰到叶子就停最小深度的天然解法其实最小深度用层序写反而更符合直觉。因为层序是从上往下一层一层扩第一次碰到叶子节点时当前的深度就是最小深度。你可以想象成“从水面往下看哪条树枝最短先露出水面”BFS 天然就是按距离向外扩展的。int minDepth(TreeNode* root) { if (root nullptr) return 0; queueTreeNode* que; que.push(root); int depth 0; while (!que.empty()) { int size que.size(); depth; for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); if (node-left nullptr node-right nullptr) { return depth; } if (node-left) que.push(node-left); if (node-right) que.push(node-right); } } return depth; }面试里如果让我手写 111我大概率会先给这个层序版本不容易踩边界一讲面试官就懂。然后我会提一句“递归版本我也能写”再补上正确版递归代码。两套解法之间正好体现你对 DFS 和 BFS 两种思路都拿得下。4. 116/117 填充 next 指针从标准模板到空间优化4.1 层序遍历的解法五分钟也能写完116 题是在每个节点上多了一个 next 指针要求把它指向同一层右侧相邻节点。最无脑的方法就是层序遍历在每一层的 for 循环里用一个 pre 指针把节点串起来Node* connect(Node* root) { if (root nullptr) return root; queueNode* que; que.push(root); while (!que.empty()) { int size que.size(); Node* pre nullptr; for (int i 0; i size; i) { Node* node que.front(); que.pop(); if (pre) pre-next node; pre node; if (node-left) que.push(node-left); if (node-right) que.push(node-right); } pre-next nullptr; } return root; }pre 每层初始化一次循环里 pre 先指向左侧节点再指向右侧节点。这个解法空间复杂度 O(n)对于 LeetCode 的难度判定完全合格。我记得在训练营群里不少人做完这题后觉得“不过如此”然后直接跳过 117 去刷下一章了。但我劝你别跳因为 117 才是真正拉开差距的地方。4.2 面试官追问“能不能 O(1) 空间”时的思路如果面试官在 116 后面补一句“能不能不用队列”很多人会愣住。答案是可以关键在于利用我们已经构造好的 next 指针。思路是这样。根节点已经是第一层next 暂时为空。我们从第一层开始依次处理每一层遍历当前层的链表把当前层每个节点的左右孩子按顺序连接起来形成下一层的链表然后移动到下一层最左边的节点继续重复。116 给的是满二叉树所以可以很朴素地写Node* connect(Node* root) { if (root nullptr) return root; Node* leftmost root; while (leftmost-left) { Node* head leftmost; while (head) { head-left-next head-right; if (head-next) { head-right-next head-next-left; } head head-next; } leftmost leftmost-left; } return root; }这段代码的核心是head 指针沿着上一层已经连好的 next 链走每到一个节点就负责连好它的左右孩子。做完一整层后leftmost 切到左孩子继续下一层。但 117 不是满二叉树有些节点没有左孩子或右孩子上面的写法就会崩。通用的处理方式是引入一个虚拟头节点 dummy每一层都用 dummy 来收集非空子节点Node* connect(Node* root) { if (root nullptr) return root; Node* head root; while (head) { Node dummy(-1); Node* tail dummy; for (Node* cur head; cur ! nullptr; cur cur-next) { if (cur-left) { tail-next cur-left; tail tail-next; } if (cur-right) { tail-next cur-right; tail tail-next; } } head dummy.next; } return root; }这段代码对 116 和 117 都成立因为它不假设每个节点都有两个孩子只把存在的孩子节点串起来。dummy 节点在这里起的作用类似链表题里常见的虚拟头节点能省掉对“下一层第一个节点是谁”的额外判断。4.3 这组题真正在考你什么116/117 表面上是层序遍历的应用实际上在逼你思考一件事层与层之间的连接能不能在遍历上层时就顺便建好用队列实现代码简单但空间是 O(n)用 next 指针逐层推进代码复杂一些空间却能做到 O(1)。面试官问“能不能优化空间”通常不是要你背那套 O(1) 的代码而是想看你能不能意识到“队列里有大量节点其实已经被 next 指针表达了”。我在刷这一题时最大的体会是别急着背 O(1) 版本先把普通层序版本写到条件反射然后再去想优化。很多人一上来就啃 O(1)结果连普通版都写不顺面试时反而两头空。5. 二叉树题最容易踩的运行时错误以及调试心法5.1 为什么写二叉树程序时总是报运行时错误“写二叉树程序时为什么总是报运行时错误”这个问题常见搜索里年年有人问训练营群里也几乎每天出现。我总结下来最常见的原因就三类全都能提前规避。第一类也是最多的一类空指针访问。二叉树的节点结构天然有大量“可能为空”的左孩子右孩子你如果写node-left-val必须先确认node-left不为空。递归调用时也是一样函数入口不判断root nullptr一调用就崩。第二类递归的终止条件写错。有很多递归模板看起来差不多但终止条件从if (root nullptr)变成if (root-left nullptr root-right nullptr)语义就差很多。比如最小深度如果你用叶子的条件去终止那遇到空节点就不会触发逻辑会绕来绕去。第三类递归函数返回值或参数类型跟声明不一致。比如你声明了一个返回 int 的函数中间某个分支忘记 return编译会报警告运行时行为就不可预期。树相关问题的递归往往很长要养成每个分支都确认有 return 的习惯。5.2 我自己的调试三步法既然在训练营里刷题最好别依赖 IDE 的重型调试器。我的做法一直很朴素但很管用。第一步准备一棵固定小树。比如[1,2,2,3,null,null,3]这棵树结构简单又有左右不对称的分支足够暴露大多数问题。每写一个二叉树相关的函数先在脑内或纸上把这棵树的递归调用过程走一遍。第二步在关键节点打印。递归函数里打印当前节点的值和当前深度配合“调用栈缩进”的基本打印方式几乎立刻能看出递归在哪个分支跑偏。我这里说的打印不是重定向调试器就是最基础的cout输出。第三步把出错的测试用例输入进去一行一行跟着代码走。对二叉树题来说最常见的运行错误就是空指针而空指针一定发生在你对某个节点的 left/right 直接取值时。顺着用例走一遍发现哪个节点没有子节点就能定位问题。5.3 从二叉树 part02 往后看递归与回溯的铺垫DAY14 的评论区里经常有人问“层序学完了下一步是不是就轻松了”我的答案比较直接千万不要掉以轻心。二叉树 part02 之后训练营会进入路径总和、平衡二叉树、所有路径这类题目它们真正考验的是递归内部的回溯逻辑。层序遍历练的是“按层处理”的思维它和深度优先配合起来才是完整的树型算法能力。今天的模板练得越扎实后面写回溯时越不容易乱。因为回溯本质上就是深度优先搜索的一种实现方式而你对树的两种遍历维度越熟面试时遇到“树的直径”“最近公共祖先”这类变形题才越有可能在几分钟内找到正确方向。我在训练营打卡到 DAY14 时的感受是二叉树的前中后序遍历让我“认识了树”而 part02 的层序和深度问题让我开始“使用树”。这种转变不是一个瞬间完成的但它从这一天的练习开始变得越来越明显。刷题到这个阶段最重要的已经不是追求数量而是把每一个模板背后的原因吃透下次看到同类题时一眼就能认出它是谁的孩子。