二叉树递归进阶：平衡、路径、左叶子与完全二叉树计数

代码随想录训练营刷到第13天，二叉树模块终于开始动真格的了。今天的四道题——110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和、222.完全二叉树的节点个数——没有引入任何新概念，用到的全是前面几天反复练习过的递归模板和遍历顺序，但每一道都在逼你想清楚同一件事：在遍历一棵树的过程中，你究竟要从子节点带回什么信息、又要把什么状态往下传。想明白这一点，是你从"会背模板"走向"会做题"的分水岭。

四道题单看都不算难，但组合在一起，刚好把二叉树题目里最常出现、也最容易翻车的四类考点全覆盖：高度与深度的计算方向、回溯路径的维护方式、基于父节点做条件判断、利用特殊树的结构性质做复杂度优化。

这篇文章我把自己刷完这一天的解题笔记、完整代码和踩坑记录全整理出来。不管你是跟着训练营一起刷的，还是自己刷 LeetCode 到二叉树模块卡住了，都可以直接参考其中的思路和实现。

1. 四道题串起来看：这一天到底在练什么

1.1 从遍历模板到"遍历的工程化应用"

前十二天的内容，核心任务是把树的各种遍历方式练熟：层序用队列，前序中序后序用递归或栈，模板背得滚瓜烂熟。但能"把一棵树完整走一遍"和能"在遍历中解决实际问题"是两码事。第13天的四道题，恰好就是从前者过渡到后者的第一组题目。

110.平衡二叉树，要求你在遍历的过程中顺便算出每个节点左右子树的高度差，并判断是否合法；257.二叉树的所有路径，要求你在遍历的过程中维护一条从根到当前节点的路径，到叶子节点时把整条路径输出；404.左叶子之和，要求你在遍历时针对特定类型的节点做筛选和累加；222.完全二叉树的节点个数，则要求你在遍历的时候利用树的特殊结构去跳过一部分不需要访问的节点。

这四种需求，几乎覆盖了二叉树非模板题的所有提问方式：算值的、收集路径的、按条件过滤的、利用结构剪枝的。所以这一天在训练营的课程表里位置很特殊——它是"遍历模板"和"树形问题"之间的桥梁。

1.2 四道题的难度梯度与考察侧重点

用一张表把这四道题放在一起看，对比会更清楚：

从面试角度看，110 几乎是树形 DP 的入门题，大厂笔试和小公司面试都常见；257 是回溯思想的经典载体，尤其适合作为"能不能把路径想清楚"的筛选题；404 属于细节题，考察你有没有被"左叶子"这个名词带偏；222 则是典型的"数据结构性质题"，考察你能否从完全二叉树的定义里挖出优化空间。

把这四道题的定位搞清楚之后，我建议按上面表格的顺序刷。前面一道题用到的后序遍历思路，在后面的题目里会反复出现，按这个顺序练习，知识是叠加的，而不是零散的。

2. 110.平衡二叉树：用-1哨兵一次后序遍历判断到底

2.1 高度和深度先搞明白，不然后面全乱

"平衡二叉树"的判定条件是：对树中的任意节点，它的左子树高度和右子树高度之差不能超过1。注意，这里说的是"任意节点"，不是只检查根节点。很多初学者会只检查根节点左右子树的高度差，结果一棵局部不平衡的树被误判为平衡树。

要正确处理"任意节点"，就必须在递归的每一层都做校验。而核心概念有两个：高度（height）和深度（depth）。

• 深度是从根出发往下数的，根节点的深度是0，越往下越大；
• 高度是从叶子出发往上数的，空节点高度是0，叶子节点高度是1，越往上越大。

在代码层面，求深度适合前序（自上而下传递），求高度必须后序（自下而上汇总）。为什么？因为高度需要先知道子树的情况才能算出来：当前节点的高度等于 max(左子树高度, 右子树高度) + 1。这是一个从子节点结果推导自身的过程，天然就是后序。

平衡二叉树这题问的是高度差，所以正确的递归骨架必须是后序：先拿左右子树的高度，再判断当前节点是否平衡，最后把当前节点的高度返回给上一层。理解了这一点，代码基本不会写歪。

2.2 朴素写法为什么会退化到O(n²)

先看一种很直觉的写法：写一个 getHeight 函数计算高度，再写一个 isBalanced 递归判断每个节点是否平衡。

int getHeight(TreeNode* node) { if (node == nullptr) return 0; return 1 + max(getHeight(node->left), getHeight(node->right)); } bool isBalanced(TreeNode* root) { if (root == nullptr) return true; int leftHeight = getHeight(root->left); int rightHeight = getHeight(root->right); if (abs(leftHeight - rightHeight) > 1) return false; return isBalanced(root->left) && isBalanced(root->right); }

逻辑完全正确，但有一个明显的性能缺陷：isBalanced 在递归检查每个节点时，每个节点又都会调用 getHeight 把整棵子树重新扫一遍。最坏情况下，比如一棵链状的树，每个节点的高度计算都要遍历剩余的所有节点，总复杂度会退化到 O(n²)。

LeetCode 这题的数据范围是节点数不超过 5000，O(n²) 在极端的测试数据下确实可能超时。但更重要的是面试场景：你给出这个版本，面试官几乎一定会问"能不能优化"。优化方向不是换一种遍历方式，而是把"算高度"和"查平衡"两个职责合并到一次后序遍历里。合并的关键，就是用一个特殊返回值标记"不平衡"。

2.3 哨兵返回值：一次遍历搞定计算和校验

完整代码（C++）：

class Solution { public: bool isBalanced(TreeNode* root) { return getHeight(root) != -1; } private: int getHeight(TreeNode* node) { 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; // 右子树已经不平衡，直接上抛 if (abs(leftHeight - rightHeight) > 1) return -1; // 当前节点不平衡 return max(leftHeight, rightHeight) + 1; // 正常返回高度 } };

每次递归先处理左子树，再处理右子树，最后处理当前节点——这是标准后序。返回值有两种含义：正常时返回当前子树的高度，异常时返回 -1。上层拿到 -1，说明整个子树已经不满足平衡条件，不用再往下判断了。

为什么用 -1 而不是别的值？因为高度永远是非负整数，-1 在这个语义空间里是天然的安全哨兵。你可以在所有"发现不平衡"的路径上都返回 -1，保证它不会和合法高度冲突，也不用额外开一个全局变量去记录状态。

这套"正常返回值 + 哨兵异常值"的写法，在后面很多树形 DP 题里都会用到。比如计算二叉树直径、判断对称二叉树、求最近公共祖先时，都可能需要一个特殊返回值来表示"这条路走不通"。提前在平衡二叉树这题把模式练熟，后面会省很多力。

Java 和 Python 的翻译也很直接：Java 用 int + -1，Python 里同样用 -1 作为哨兵，唯一要注意的是把 abs 和 max 换成对应语言的内置函数。逻辑完全一致，换成你熟悉的语言写一遍，理解会更扎实。

3. 257.二叉树的所有路径：回溯模板就藏在这道题里

3.1 路径问题的核心：谁在记录"我从哪来"

110 练的是"从子节点汇总信息"，到了 257 这里方向完全反过来了：要把信息从根一路传到叶子。题目要求输出所有根到叶子的路径，格式如 "1->2->5"。树的路径问题，在思维上可以拆成两部分：路径怎么生长，以及路径在哪里结算。

路径是从根开始生长的，每递归进入一个节点，这个节点的值就要被追加到当前路径的末尾。所以路径的生长方向与前序遍历天然匹配：先处理当前节点，再把路径往下传。这也是为什么树路径问题几乎都用前序而不是后序。

但有一个细节很容易忽略：递归返回到上一层时，当前节点已经从逻辑上"离开"了这条路径，它的值不应该再出现在路径里。这就是回溯的核心——状态要随着递归的进入而追加，随着递归的返回而撤销。如果你不在返回前把当前节点从路径里撤掉，路径就会被污染：左子树走过的节点会被残留在右子树的路径里，输出的路径就会多出一截谁都不认识的节点。

3.2 标准回溯模板：vector path + 显式pop_back

下面是我的写法，也是代码随想录训练营里推荐的标准版：

class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; vector<int> path; if (root == nullptr) return result; traversal(root, path, result); return result; } private: void traversal(TreeNode* node, vector<int>& path, vector<string>& result) { path.push_back(node->val); // 前序：路径先记录当前节点 if (node->left == nullptr && node->right == nullptr) { string s; for (int i = 0; i < path.size() - 1; i++) { s += to_string(path[i]) + "->"; } s += to_string(path[path.size() - 1]); result.push_back(s); return; // 叶子节点直接结算，回到上一层再统一回溯 } if (node->left) { traversal(node->left, path, result); path.pop_back(); // 递归返回，撤销左子树带来的状态 } if (node->right) { traversal(node->right, path, result); path.pop_back(); // 同理，撤销右子树带来的状态 } } };

解释一下为什么 pop_back 必须紧跟在递归调用后面。这里 path 是引用传递的，整棵递归树共享同一个 vector。进入某个子节点前 push_back 一次，递归返回后如果不清掉，下一次进入兄弟节点时 path 里仍然留着上一个子树的值，最终每条路径都会多出一截不属于自己的节点。

另一个容易困惑的点：叶子节点 push_back 之后没有立刻 pop_back，谁负责清理？答案是父节点。当 traversal(node->left) 返回时，父节点那一层紧接着执行 path.pop_back()，把叶子节点从 path 中弹掉。这个"上层负责收回"的约定，是回溯递归里非常关键的设计——你把状态追加给别人，你也要负责在返回后撤销。

3.3 字符串传值的简化版：省事但学不到回溯

如果直接用 string 作为 path，每次递归传值拷贝，可以少写 pop_back，代码短了很多：

class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; if (root == nullptr) return result; dfs(root, "", result); return result; } void dfs(TreeNode* node, string path, vector<string>& result) { if (node == nullptr) return; path += to_string(node->val); if (node->left == nullptr && node->right == nullptr) { result.push_back(path); return; } path += "->"; dfs(node->left, path, result); dfs(node->right, path, result); } };

这版本的"回溯"是隐式的——每次递归创建新的 string，返回后旧变量自动作废，状态自然恢复。逻辑简洁，可读性也好，257 题的数据范围（节点数最多100）完全跑得动。

但我依然建议在训练阶段先写引用+回溯的版本。原因很简单：后面的回溯算法章节才是重头戏。组合、排列、子集这些问题里，路径的状态不能依赖字符串值拷贝解决，必须用引用 + pop_back 手动维护。树的路径问题是练习这套技能最好的场景，因为树的结构天然给了明确的进入和返回时机。你在 257 上练熟了"push_back + 递归 + pop_back"的节奏，后面写 permutations 时会顺手很多。

而且面试官如果追问"为什么用引用传 path"，你能讲出"因为要显式回溯，避免兄弟子树之间的状态污染"，这比只交一个值拷贝版本更能体现对递归原理的理解。

4. 404.左叶子之和：判定条件要写在父节点上

4.1 站在叶子上看不清自己是谁

练完汇总（110）和传递（257）两种方向，第三道题加了一点刁钻的细节。"左叶子之和"的题意直白：把所有满足"左叶子"条件的节点值加起来。但"左叶子"这个词藏了一个初学者最容易掉进去的陷阱。

左叶子需要同时满足两个条件：

• 它是一个叶子节点，也就是没有左孩子也没有右孩子；
• 它是某个节点的左孩子。

问题在于：当你站在一个叶子节点上，你完全没有信息判断自己是左孩子还是右孩子。你自己的视角里只有"我是不是叶子"，没有"我在父节点的哪一边"。方向是相对父节点才存在的，所以判断逻辑必须上移到父节点那一层——检查当前节点是否存在一个"左孩子，并且那个左孩子本身是叶子"。

这个"站在父节点看子节点身份"的思路，是这类题目和普通遍历最大的差别。很多人卡在 404 上，不是不会遍历，而是思维没有完成从"节点本位"到"关系本位"的切换。树的很多条件判断都是关系性的：左叶子是父子关系，右视图是层级关系，最近公共祖先也是祖先-后代关系。尽早建立这个视角，后面读树题会轻松很多。

4.2 判定逻辑怎么写：三种遍历次序都能做

递归实现上，我推荐后序版本，因为结构最统一：

class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root == nullptr) return 0; int leftSum = sumOfLeftLeaves(root->left); int rightSum = sumOfLeftLeaves(root->right); int cur = 0; if (root->left && root->left->left == nullptr && root->left->right == nullptr) { cur = root->left->val; // 左孩子是叶子，它就是当前子树能贡献的左叶子 } return leftSum + rightSum + cur; } };

这个函数的语义是：返回以 node 为根的子树中所有左叶子的和。递归的三段分别是：左子树里有多少左叶子，右子树里有多少左叶子，当前节点自己能不能额外贡献一个左叶子（也就是它的左孩子是不是左叶子）。

注意一个边界：成立条件是root->left && root->left->left == nullptr && root->left->right == nullptr，三个条件一个都不能少。少了 root->left，空指针解引用直接崩；少了后面任何一个，非叶子的左孩子也会被误算进来。这个三条件判断就是整道题唯一的考点，写对它就通过了。

后序版本里，函数本身要返回子树的累加结果，用哪种遍历顺序最终结果都一样。你可以试试把返回挪到递归之前，就是前序版本，同样能 AC。真正重要的只有那个判定条件的位置和完整性。

如果偏好迭代，用栈模拟前序完全没问题，判定条件一字不差：

class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root == nullptr) return 0; stack<TreeNode*> st; st.push(root); int sum = 0; while (!st.empty()) { TreeNode* node = st.top(); st.pop(); if (node->left && node->left->left == nullptr && node->left->right == nullptr) { sum += node->left->val; } if (node->right) st.push(node->right); if (node->left) st.push(node->left); } return sum; } };

迭代版每次从栈里弹出一个节点，马上检查它有没有左叶子孩子，有就加上。栈的顺序不影响结果，因为每条边都只会被它的父节点检视一次，左叶子的判定天然和遍历顺序无关。

5. 222.完全二叉树的节点个数：别把特殊树当普通树刷

5.1 完全二叉树的结构红利在哪

到了第四题，场景再次改变——不再强调遍历顺序，而是强调结构认知。完全二叉树的定义很严格：除最后一层外，每一层的节点数都是满的；最后一层的节点全部靠左排列。拿这个定义对比普通二叉树，你会发现完全二叉树的形状被约束得非常死，而这种约束正是优化的机会。

最朴素的解法是暴力数：递归遍历每个节点，O(n)。n 如果只有几千，这题明显能过——LeetCode 当前给的节点数上限是 5×10⁴，暴力也不超时。但题目既然特意告诉你"这是完全二叉树"，就说明出题人期望你利用它。

关键观察是：如果从某个节点出发，沿着最左路径走到底的深度和沿着最右路径走到底的深度相等，那么以这个节点为根的子树一定是一棵满二叉树——每一层都填满了。满二叉树的节点总数可以直接用公式：层数为 h 时，节点数等于 2^h - 1。这样一整棵满子树就不需要逐个节点去访问了。

算法可以这样设计：每到一个节点，先量一量左右边界深度；如果相等，说明整棵子树是满的，套公式直接返回；如果不等，说明当前子树没有填满，继续往左右子树递归。递归到某个深度时，遇到满子树就停住，用公式收割结果。

5.2 完整代码与复杂度推导

class Solution { public: int countNodes(TreeNode* root) { if (root == nullptr) return 0; int leftDepth = 0, rightDepth = 0; TreeNode* leftNode = root->left; TreeNode* rightNode = root->right; while (leftNode) { // 沿着最左路径往下走，数边数 leftNode = leftNode->left; leftDepth++; } while (rightNode) { // 沿着最右路径往下走，数边数 rightNode = rightNode->right; rightDepth++; } if (leftDepth == rightDepth) { return (2 << leftDepth) - 1; // 等价于 2^(leftDepth+1) - 1 } return 1 + countNodes(root->left) + countNodes(root->right); } };

解释一下位运算。leftDepth 统计的是从当前节点的左孩子一路往左下走的边数。如果左右深度相等，当前子树的层数是 leftDepth + 1，满二叉树的节点数就是 2^(leftDepth+1) - 1。2 << leftDepth就是把 2 左移 leftDepth 位，相当于 2^(leftDepth+1)，所以(2 << leftDepth) - 1就是这个公式的紧凑写法。如果不习惯位运算，写成(1 << (leftDepth + 1)) - 1更直白。

用一棵 6 个节点的完全二叉树走一遍流程：根节点下有左子 L、右子 R，L 有两个孩子 LL、LR，R 有一个孩子 RL。

• 在根节点：左边界路径是 L→LL，leftDepth = 2；右边界路径是 R，RL 的右侧没有节点，rightDepth = 1。不相等，不能套公式。
• 递归左子树 L（以 L 为根，有 LL、LR 两个满孩子）：leftDepth = 1，rightDepth = 1，相等，按公式直接返回 3 个节点（2² - 1 = 3），不用往下走了。
• 递归右子树 R（以 R 为根，只有一个左孩子 RL，没有右孩子）：leftDepth = 1，rightDepth = 0，不相等。继续递归到 RL：左右深度都为 0，返回 1；R 的右孩子为 null，返回 0。所以 R 子树总数为 1 + 1 + 0 = 2。
• 整个树的总数 = 根自身的 1 + 左子树 3 + 右子树 2 = 6。

这个例子很直接地展示了优化效果：整棵左子树只量了两次深度就立刻出结果，没有逐个节点访问；右子树也算是最小规模的递归。真正的大数据量下，这个剪枝能省掉大量无效遍历。

复杂度分析：每次进入节点，都需要花 O(h) 的时间测量左右边界深度。对于一个完全二叉树，递归到某个节点后，左右子树中至少有一个是满的，可以直接用公式返回，因此需要继续递归的分支会迅速减少。总的递归深度是 O(log n)，每个递归层级上的测量总耗时也不会超过 O(log n)，所以整体的时间复杂度是 O(log²n)，空间复杂度是递归栈的 O(log n)。

5.3 暴力解虽然能过，为什么还要学优化

我知道很多人刷这道题时会有疑问：LeetCode 上节点数上限是 5×10⁴，直接写 count(root) = count(root->left) + count(root->right) + 1 也能 AC，为什么要费劲学这个"满二叉树公式"版本？

我从训练营和面试两个角度说下自己的理解。

从训练营的角度：这四道题是一个递进。前面几道题练的是"如何把遍历用好"，222 练的是"如何看出可以用数学跳步"。如果你只满足于 AC 一个暴力解，那这一天的最后一题就没有任何增量价值。真正值得吸收的，是"观察结构性质 → 把性质变成剪枝条件 → 用公式接管重复劳动"这个思维链路。

从面试的角度：出了这题，面试官真正想看的不是你数节点数数得快，而是你会不会利用题面已经告诉你的"完全二叉树"这个性质。你在面试里如果主动说"我可以先暴力 O(n) 保底，然后再用满二叉树公式优化到 O(log²n)"，传递出来的信号是：我不只会写模板，我还会针对数据结构特性做复杂度分析。这种信号在很多场景下比 AC 本身更有价值。

当然，暴力解也有存在意义——它是你思路断掉时的兜底。我自己的习惯是：先确保暴力解不出错，再在暴力解的基础上加剪枝。这样即使优化部分写错了，至少能保底拿分。

6. 常见问题与排查技巧实录

6.1 四道题最容易踩的坑一览

我把实际刷题时收集到的坑整理成一个速查表，每一个都是真实发生过的：

除了表里这些，还有一个很隐蔽的细节：110 的剪枝不完整。有人写了 -1 哨兵，但在拿到 leftHeight 之后没有立刻检查，而是继续调 rightHeight。这在语义上没错，但浪费了一次递归。正确写法是拿到左子树结果先判断一次，拿到右子树结果再判断一次，见 -1 就立刻 return，把剪枝效果做满。

257 的字符串拼接也容易出格式问题。如果每一层都先把 "->" 拼在节点值后面，最后一个叶子的值后面会多出一个 "->"。我常用的规避方法是：像上面的代码那样，到叶子统一拼接；或者先收集到 vector 里，到叶子再统一格式化。别在中间步骤贪图省事。

222 的溢出问题也值得提一句。虽然当前数据范围不会触发，但(2 << leftDepth)在 leftDepth 较大时会超过 32 位 int 的上界。面试时可以主动提一句"这里用 long long 更稳"，这是加分项。

6.2 递归调试三板斧

树的递归题，我调试用的是三个土办法，实测比纯看代码快很多。

第一招：打印递归轨迹。在函数入口打印节点值和当前递归深度，在返回前打印返回值。可以用一个字符串把深度可视化：

void debug(TreeNode* node, int depth) { if (node == nullptr) return; cout << string(depth * 2, '-') << node->val << endl; debug(node->left, depth + 1); debug(node->right, depth + 1); }

这个缩进输出能直接看出递归的进入和返回顺序，特别适合排查 257 这类路径问题——你能肉眼看到路径是在哪里被错误保留、在哪里被错误弹掉的。

第二招：准备一组最小的边界用例。树的题，边界用例其实非常固定：空树、只有一个节点的树、左斜树、右斜树、满二叉树、完全但不满的树。每道题刷完，把这几个用例跑一遍，基本能把隐藏 bug 全部暴露出来。比如 404 的判定，用一棵三节点的树（根 + 左叶 + 右叶）就能立刻验证左叶子有没有被正确累加。

第三招：递归和迭代互验。同一道题分别写递归和迭代版本，用随机生成的树跑对比。如果两个版本结果不一致，通常问题出在遍历顺序或者状态恢复的时机上。这个办法对 257 尤其管用，因为回溯阶段的时机错误很容易被版本间的差异暴露出来。

提示：刷树题最忌讳的是盯着代码空想。我一般建议先画一棵不超过四层的小树，把递归的调用顺序在纸上推一遍，再去和代码的打印结果对。纸上能推对，代码基本就不会错。

最后分享一点我自己的体会。刷完第13天这四道题，我最大的变化不是记住了四个模板，而是形成了一个新的思考习惯：每个树题读完，我会先问自己三个问题——当前节点要从子节点拿到什么信息？当前节点自己要贡献什么信息？这些信息该往上返回，还是往下传给子节点？

110 要的是从子节点拿高度和合法性；257 要的是把路径往下传给子节点；404 是要从子节点拿求和结果、同时自己判断左叶子；222 则是要从子节点拿节点数，但同时利用满树公式跳过计算。一旦这三个问题想清楚，代码怎么写几乎是水到渠成的事。

这也是训练营这个阶段最值钱的东西——不是在练代码，是在练建模。如果你也在这四道题上反复卡壳，别急着看题解，先把上面三个问题写在纸上，想明白再动手，效果会比背十遍题解都好。