企业官网建设流程全解析

训练营第13天，二叉树part03，这一天的三道题——110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和——刚拿到手时我还有点轻敌，毕竟前面两天的翻转、对称、层序都算顺利。真正刷完才发现，这三道题是递归从"照着模板写"过渡到"理解模型自己设计"的关键分水岭。它们分别对应递归里三种典型的信息流动方式：从子树向上返回结果、从上向下携带路径并回溯、以及在父节点判断子节点的特征。这篇就把三道题的设计思路、完整代码、调试经验全盘写出来，给正在刷二叉树part03的同学一份能直接照着复盘的笔记。

1. 三道题为什么放在同一天：先弄懂这一天的编排逻辑

1.1 三道题共享的知识基线

part01和part02里，你已经掌握了递归遍历、迭代遍历、层序遍历框架，以及翻转二叉树、对称二叉树这类"在递归过程中交换或比较节点"的题。到part03，难度从"单个递归过程"升级到"递归过程中要维护额外状态"，但这个升级不是平白无故的，它踩在三道题的共同基线上：第一，能用递归出口处理空节点；第二，知道递归函数每一层返回什么、做了什么；第三，能区分"处理当前节点"和"处理子树"的分工。

我记得第一天刷平衡二叉树时没在意这个基线，直接上手写，结果写出了"每个节点都重新算一遍子树高度"的O(n^2)版本。后面对照训练营的思路复盘，才意识到递归应用题的第一步不是写代码，而是先想清楚三件事：递归的返回值到底代表什么、单层逻辑要把什么信息往上传、以及每一层递归结束后凭什么保证状态被正确恢复。part03的三道题，本质上就是在反复训练这三件事。

1.2 三种递归模型，三种信息流动方式

这一天真正值得记下来的，是三道题分别代表三种不同的递归模型，我习惯把它们叫做"自底向上返回型""自顶向下携带型"和"父节点判定型"。

为什么平衡二叉树必须自底向上？因为一个节点是否平衡，取决于它的左右子树各自平不平衡、高度差是多少，这些信息只有孩子知道，父节点拿不到，所以只能靠递归返回值一层一层往上传。为什么路径题必须自顶向下？因为从根到当前节点的路径，是在往下走的过程中逐步累积出来的，走到叶子时直接输出即可。左叶子之和则更像一个"视角题"，单个节点永远不知道自己是不是左孩子，答案只存在于父节点的判断里。这三道题刷完，你对递归返回值、递归参数、递归出口的理解会被同时逼到下一个层次。

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, vector<int>& path, vector<string>& 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(); } } vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; vector<int> path; if (root == nullptr) return result; traversal(root, path, result); return result; } };

拿一棵简单树推演一下，规则是：1是根，左孩子2，2的右孩子5，1的右孩子3。

第一步，traversal(1)，path变成[1]；第二步，进入左分支traversal(2)，path变成[1,2]；第三步，2没有左孩子，进入右分支traversal(5)，path变成[1,2,5]，5是叶子，拼出"1->2->5"存入结果后返回。注意此时5并没有自己pop，pop动作发生在它的调用者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 高频报错与错误的速查表

刷题过程中踩过的坑，我用一张表记下来，训练营里分享给同学后反响很好，这里直接给出来：

这些错误我几乎都犯过一遍，尤其是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天是递归的分水岭，之前写递归靠模仿，之后写递归靠模型。如果你今天刷完也觉得"看答案能懂、自己写就卡壳"，这是正常的，说明你正在从"背模板"过渡到"设计递归"的过程中。再分享一个小技巧：把三道题放进同一页笔记，分别写下"返回值是什么、出口是什么、共享状态怎么维护"，之后刷任何一道新的二叉树递归题，都先填这三栏。填得出来，代码基本就有了；填不出来，先把思路补到能填出来再动手。这个习惯我一直保留到训练营后期，几乎所有二叉树的递归题都能靠这三栏快速建立骨架。