训练营第13天二叉树part03这一天的三道题——110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和——刚拿到手时我还有点轻敌毕竟前面两天的翻转、对称、层序都算顺利。真正刷完才发现这三道题是递归从照着模板写过渡到理解模型自己设计的关键分水岭。它们分别对应递归里三种典型的信息流动方式从子树向上返回结果、从上向下携带路径并回溯、以及在父节点判断子节点的特征。这篇就把三道题的设计思路、完整代码、调试经验全盘写出来给正在刷二叉树part03的同学一份能直接照着复盘的笔记。1. 三道题为什么放在同一天先弄懂这一天的编排逻辑1.1 三道题共享的知识基线part01和part02里你已经掌握了递归遍历、迭代遍历、层序遍历框架以及翻转二叉树、对称二叉树这类在递归过程中交换或比较节点的题。到part03难度从单个递归过程升级到递归过程中要维护额外状态但这个升级不是平白无故的它踩在三道题的共同基线上第一能用递归出口处理空节点第二知道递归函数每一层返回什么、做了什么第三能区分处理当前节点和处理子树的分工。我记得第一天刷平衡二叉树时没在意这个基线直接上手写结果写出了每个节点都重新算一遍子树高度的O(n^2)版本。后面对照训练营的思路复盘才意识到递归应用题的第一步不是写代码而是先想清楚三件事递归的返回值到底代表什么、单层逻辑要把什么信息往上传、以及每一层递归结束后凭什么保证状态被正确恢复。part03的三道题本质上就是在反复训练这三件事。1.2 三种递归模型三种信息流动方式这一天真正值得记下来的是三道题分别代表三种不同的递归模型我习惯把它们叫做自底向上返回型自顶向下携带型和父节点判定型。题目核心问题信息流动方向关键手段110.平衡二叉树每个子树的高度差不超过1自底向上返回高度后序遍历用-1标记非法状态257.二叉树的所有路径输出根到每个叶子的完整路径自顶向下携带路径前序遍历回溯撤销选择404.左叶子之和累加所有左叶子节点值父节点判断子节点在父节点直接判定左叶子为什么平衡二叉树必须自底向上因为一个节点是否平衡取决于它的左右子树各自平不平衡、高度差是多少这些信息只有孩子知道父节点拿不到所以只能靠递归返回值一层一层往上传。为什么路径题必须自顶向下因为从根到当前节点的路径是在往下走的过程中逐步累积出来的走到叶子时直接输出即可。左叶子之和则更像一个视角题单个节点永远不知道自己是不是左孩子答案只存在于父节点的判断里。这三道题刷完你对递归返回值、递归参数、递归出口的理解会被同时逼到下一个层次。2. 平衡二叉树为什么必须用后序遍历算高度2.1 高度和深度两个容易搞反的概念先分清概念。深度是从根节点往下数根节点深度是1越往下越大高度是从叶子节点往上数叶子节点高度是1越往上越大。求一棵树是否平衡本质上是在求左右子树的高度差而高度要求你先知道叶子那一端的情况这就决定了必须用后序遍历先递归左、再递归右、最后在中间节点做判断。很多新手会把平衡二叉树写成对每个节点分别调用一个求深度的函数int maxDepth(TreeNode* node) { if (node nullptr) return 0; return 1 max(maxDepth(node-left), maxDepth(node-right)); } bool isBalanced(TreeNode* root) { if (root nullptr) return true; if (abs(maxDepth(root-left) - maxDepth(root-right)) 1) return false; return isBalanced(root-left) isBalanced(root-right); }这个写法在思路上没错但问题很大每到一个节点都会把它的整棵子树重新遍历一遍遇到一棵严重倾斜的树时间复杂度会退化成O(n^2)。训练营的标准做法是让递归函数在一次遍历里同时完成算高度和检查是否平衡两件事这就要用到-1这个哨兵值。2.2 用-1哨兵同时完成判断和剪枝递归函数返回值的含义可以设计成如果子树平衡返回该子树的高度如果不平衡返回-1。这样一来父节点只拿到两个信息左边来自子树的高度以及子树是否出问题。-1这个值在正常高度里不可能出现所以它天然是一个异常标记。更好的地方在于-1还能起到剪枝作用。我处理左子树时如果发现已经返回-1整个树已经不可能平衡了右子树就不用再递归了直接向上抛-1。这个提前退出的细节很多人写出来但不讲实际上它在极端倾斜的树上能省掉大量无谓的递归调用。2.3 完整实现与复杂度分析class Solution { public: int getHeight(TreeNode* node) { // 递归出口空节点高度为0 if (node nullptr) return 0; // 先算左子树如果已经不平衡直接上抛 int leftHeight getHeight(node-left); if (leftHeight -1) return -1; // 再算右子树 int rightHeight getHeight(node-right); if (rightHeight -1) return -1; // 高度差超过1当前节点判定为不平衡 if (abs(leftHeight - rightHeight) 1) return -1; return max(leftHeight, rightHeight) 1; } bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; } };这个版本的时间复杂度是O(n)每个节点最多访问一次递归栈深度取决于树高最坏情况下退化成一条链时为O(n)。我实际在测试用例里跑的时候明显感觉到先检查左子树再检查右子树这个顺序还带来一个隐藏收益很多不平衡的情况在左子树就暴露了右子树的递归根本不会执行。如果你想把这种剪枝利用到极致可以在工程代码里把大概率不平衡的那一侧放在前面检查。3. 二叉树的所有路径回溯的第一堂正课3.1 为什么路径必须做回溯这道题要求输出从根到每个叶子的完整路径。直觉上就是一直往下走、走到头就记录但问题在于当你从2号节点回到1号节点、再去访问3号节点时路径容器里必须把2号节点清掉否则3号节点的路径会变成1-2-3这种错乱结果。这个把已经访问过的节点从当前路径中移除的操作就是回溯。我见过最典型的错误写法是递归函数里往path里添加了节点但递归返回后忘了pop结果第二天的路径带着前一个分支的残留节点。你可以这样理解回溯递归往下走的时候每一层都往背包里放一件东西返回上一层的时候必须把东西拿出来否则下层带进去的东西会污染兄弟分支的旅途。这个拿出去的动作就是pop_back。3.2 用vector存路径还是用string直接拼训练营的参考实现用的是vector 保存路径走到叶子节点时再统一拼成字符串。这样做的理由是字符串拼接本身有开销如果每一层都往string后面追加-路径一旦很长中间状态会被反复复制用vector只存整型复制成本低回溯时pop一下干净利落。当然也有更简单的写法把路径作为值传递的string在递归调用时传入path - to_string(val)这样天然不需要pop因为每一层拿到的是新副本。这个写法代码更短但每深入一层就会产生一次字符串拷贝路径很多且很深时性能不好。我建议第一遍刷题用vector回溯的标准版把回溯动作刻进肌肉记忆等彻底理解了再去玩string副本的写法。3.3 完整实现与一次递归过程推演class Solution { public: void traversal(TreeNode* node, vectorint path, vectorstring result) { // 前序先把当前节点值放进路径 path.push_back(node-val); // 到达叶子节点把path拼成字符串 if (node-left nullptr node-right nullptr) { string sPath; for (size_t i 0; i path.size() - 1; i) { sPath to_string(path[i]); sPath -; } sPath to_string(path.back()); result.push_back(sPath); return; } // 有左孩子才递归返回后撤销 if (node-left) { traversal(node-left, path, result); path.pop_back(); } // 有右孩子同样递归返回后撤销 if (node-right) { traversal(node-right, path, result); path.pop_back(); } } vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; vectorint path; if (root nullptr) return result; traversal(root, path, result); return result; } };拿一棵简单树推演一下规则是1是根左孩子22的右孩子51的右孩子3。第一步traversal(1)path变成[1]第二步进入左分支traversal(2)path变成[1,2]第三步2没有左孩子进入右分支traversal(5)path变成[1,2,5]5是叶子拼出1-2-5存入结果后返回。注意此时5并没有自己poppop动作发生在它的调用者2那一层traversal(5)返回后2的右分支代码执行path.pop_back()path回到[1,2]。随后traversal(2)整体返回1的左分支调用也执行pop_back()path回到[1]。接着进入右分支traversal(3)path变成[1,3]3是叶子拼出1-3。你可以看到一条铁律谁调用递归谁负责在递归返回后清理被调用节点。叶子节点只管往path里加自己清理工作交给它的父节点。这样一级一级往下传、往上退path始终保持从根到当前节点的完整路径这个不变式。4. 左叶子之和站在父节点视角才能定义的叶子4.1 为什么左叶子不能从叶子自己判断404题的核心难点不在递归本身而在于左叶子这个定义。叶子节点很好判断左右孩子都为空。但问题来了——这个叶子节点到底是左孩子还是右孩子节点自己是不知道的它没有指向父节点的指针。所以只能反过来站在父节点的视角去判断如果当前节点的左孩子存在、且左孩子的左右都为空那么这个左孩子就是我们要找的左叶子。这个换视角的思路在二叉树里非常常见。以后你刷二叉搜索树、最近公共祖先之类的题会反复遇到节点自身信息不足必须靠父节点或祖先节点弥补的场景。我把这道题当作这类问题的入门题。要注意的是根节点永远不可能被判定为左叶子因为它没有任何父节点这也是新手容易忽略的边界情况。4.2 三种写法的对比与取舍第一种是训练营的经典写法对每个节点都返回当前左叶子值 左子树里所有左叶子值 右子树里所有左叶子值代码最对称、最好记缺点是把递归调用也打进了左叶子本身多了一次无谓调用。第二种写法是我后来优化过的遇到左叶子直接加分、不再递归进去能少走一层。第三种是迭代写法本质一样只是在显式栈里模拟父节点判断逻辑适合想练习非递归的人。写法优点缺点经典后序累加结构简单、三行核心逻辑左叶子本身仍会被递归调用一次跳过左叶子递归减少无效递归逻辑分支略多显式栈迭代避免递归栈溢出风险代码更长需要手动维护状态这三种写法我建议都写一遍。第一种用来理解递归结构第二种用来体会剪枝思路在递归里的应用第三种用来对抗一提迭代就只会层序的毛病。4.3 完整实现与边界情况class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root nullptr) return 0; int sum 0; // 站在当前节点判断左孩子是不是左叶子 if (root-left root-left-left nullptr root-left-right nullptr) { sum root-left-val; } else if (root-left) { // 左孩子不是叶子才需要继续递归 sum sumOfLeftLeaves(root-left); } // 右子树里可能藏着左叶子所以必须递归 sum sumOfLeftLeaves(root-right); return sum; } };这道题的边界情况值得单独列出来。空树返回0只有一个根节点的树返回0因为根节点不属于任何人的左叶子根节点只有左孩子且左孩子是叶子时返回该叶子值最典型的一个样例是[3,9,20,null,null,15,7]9是根节点的左叶子15是20这个节点的左叶子两个都要累加答案应该是24。我建议刷完后用这几个输入各跑一遍把左叶子的定义彻底钉死在脑子里。5. 翻车实录与调试方法三道题的高频问题排查5.1 高频报错与错误的速查表刷题过程中踩过的坑我用一张表记下来训练营里分享给同学后反响很好这里直接给出来题目典型错误原因分析修复办法110只比较根节点的左右高度差子树不平衡但没向上传递用-1哨兵子树非法就整体返回-1110每个节点重新算子树高度把深度计算和平衡判断分成了两套递归改成一次后序遍历同时完成257路径拼接出现重复或丢失分支pop_back时机不对记住谁调用谁清除铁律257字符串末尾多了-拼接循环边界写错前n-1个节点拼接箭头最后一个单独拼404把根节点也算成左叶子混淆了叶子和左叶子左叶子必须由父节点判定404左叶子被重复累加父节点判定后又递归进左叶子内部左叶子直接加分不再递归下去这些错误我几乎都犯过一遍尤其是257的pop_back时机。当时我调试到深夜输出了一个带重复节点的路径后来在纸上画出递归调用栈才发现自己把pop写在了条件判断的外面导致右分支继承了一个已经访问过的左分支节点。这类问题靠眼睛盯代码很难发现必须回到递归过程本身去推演。5.2 我的递归调试三板斧第一板斧永远先跑三节点以内的最小样例。手动在纸上画出调用顺序把每一层递归的path状态写下来比对代码实际输出。第二板斧在关键位置加打印语句比如平衡二叉树里打印每个节点的leftHeight和rightHeight路径题里打印进入和离开函数时的path内容。打印一次递归过程比盯半小时代码有效得多。第三板斧用边界输入轰炸代码空树、单节点、只有左链、只有右链、满二叉树每个都跑一遍。很多题的隐藏bug就藏在只有一个孩子这种不对称结构里。第三板斧尤其针对404题因为左这个字会让人下意识只关注左子树但右子树里的左叶子也得算对称性不对称最容易被忽略。5.3 写递归的三个自问经过这一天我把写递归前的检查清单总结成了三个问题第一这个递归函数的返回值是什么是为上层提供数据还是只做动作平衡二叉树返回高度路径题不需要返回值只做状态修改左叶子之和返回累加和——不同答案对应完全不同的写法。第二递归出口能不能覆盖所有终止条件空节点、叶子节点、或者空树这种特殊输入有没有被出口兜住第三每一层递归从哪里修改共享状态、从哪里恢复路径题里path是引用传递的共享状态修改和恢复必须成对出现。这三个自问基本上能覆盖二叉树类递归题八成以上的bug来源。训练营后面还有路径总和、构造二叉树这些更复杂的题你会发现它们的框架本质上还是这三个问题。6. 今天的模型能平移到哪些题扩展练习与复习节奏6.1 顺带就能做掉的同型题目这天的模型可以直接迁移到一批题上我按照对应关系列一下。513.找树左下角的值要么用层序遍历记录每层第一个节点要么用前序遍历加深度参数本质是自顶向下携带深度的模型。112.路径总和和113.路径总和II前者只问有没有用布尔值从下往上汇总后者要求输出所有路径几乎就是257的翻版只是多维护一个路径和。104.二叉树的最大深度和111.二叉树的最小深度最大深度就是用后序求高度最小深度要特别注意一边为空时不能简单取min否则会漏判。222.完全二叉树的节点个数如果暂时不打算用完全二叉树的性质可以先写一个通用递归版本正好练习自底向上返回计数。我当时的策略是当天不急着刷这些扩展题而是先花时间把三道主题的三种模型用自己的话讲一遍讲不明白的地方重新看代码。等到第二天再去做513和112你会发现思路顺畅得多因为它们确实只是今天模型的换皮应用。6.2 递归栈和复杂度的账三道题的递归栈深度都取决于树高满二叉树是O(logn)退化成链的树是O(n)。刷题通常在LeetCode上跑得过去但如果面试官追问能不能把递归栈省掉就要能接住。平衡二叉树可以用显式栈实现路径题也可以用栈模拟DFS但代码量会明显变大我建议先把递归版本写熟再花时间研究迭代版本。复杂度上110和404都是O(n)时间、O(h)空间257的时间复杂度要单独说遍历本身是O(n)但每次到叶子都要拼接字符串最坏情况下输出总长度能达到O(n^2)空间上除了递归栈和path还需要存结果字符串。面试里被问复杂度时把输出本身要占空间这一点讲出来能明显体现出你对问题的理解比背模板深一层。6.3 训练营节奏怎么安排复习我的建议是每道题控制在45分钟左右超过时间先看思路、再合上题解独立写。当天晚上睡前把三道题的递归模型各默写一遍代码不求一字不差但求关键步骤能顺手写出来。两天后再把这三道题重刷一遍遇到卡住的地方直接看自己写的笔记。实测这样做下来part03的掌握程度远高于当时只刷一遍就往下走的题。我个人在这个阶段最大的体会是第13天是递归的分水岭之前写递归靠模仿之后写递归靠模型。如果你今天刷完也觉得看答案能懂、自己写就卡壳这是正常的说明你正在从背模板过渡到设计递归的过程中。再分享一个小技巧把三道题放进同一页笔记分别写下返回值是什么、出口是什么、共享状态怎么维护之后刷任何一道新的二叉树递归题都先填这三栏。填得出来代码基本就有了填不出来先把思路补到能填出来再动手。这个习惯我一直保留到训练营后期几乎所有二叉树的递归题都能靠这三栏快速建立骨架。