1. 这一天练的是什么：二叉树的“规整”与“计数”
刷到训练营第15天，大部分人在这个节点已经开始上手二叉树，而且不是简单的遍历就完事，而是开始处理各种“带条件的节点筛选”。力扣110、257、404、222这四道题放在一起，其实思路非常统一：都在考察“递归返回什么”这件事。
- 110 判断一棵树是否平衡，本质是让递归返回“左边高度 vs 右边高度”的比较结果；
- 257 要求拿到所有根到叶子的路径，本质是在递归过程中维护一个路径容器；
- 404 求和所有左叶子，本质是“节点类型判定 + 条件累加”；
- 222 统计完全二叉树的节点个数，本质是把“满二叉树”的数学性质用在递归分治上。
换句话说，第15天不是让你死记四个解法，而是让你建立一种感觉：拿到一道二叉树题，先问自己三个问题——递归出口是什么？每一层递归要往上传什么？上传的信息如何被父节点利用？
我刚开始刷二叉树时特别容易犯一个毛病：拿到题就想着“我要用一个全局变量收集答案”。但到了 110 这种题，你会发现全局变量根本不好使，因为你要的不是一个最终数字，而是“这棵树合不合格”的中间状态。这四道题集中练习，正好把“返回值设计”这个基本功掰开揉碎了讲透了。
像我这样自学的，之前看任何递归都觉得神奇，直到用“递归三要素”反复套了七八道题，才慢慢敢说“哦，递归无非就是：确定返回值语义、确定结束条件、确定单层逻辑”。这一天的题目就是最好的练习场。
2. 一道一道拆：四种典型解法与选型逻辑
2.1 力扣110：高度差的“全局状态”处理
110 这道题，题目描述很简单：给定一个二叉树，判断它是否是高度平衡的二叉树。所谓高度平衡，就是每个节点的左右子树高度差绝对值不超过 1。
最容易想到的暴力做法是：写一个 getHeight 函数，然后在每个节点上分别算左子树高度和右子树高度，判断差值。这个做法没问题，但时间复杂度是 O(n²)，因为每个节点都要往下递归一遍高度。我一开始就是这么写的，提交也能过，但一看题解才发现可以有更聪明的做法。
更优的方案是“自底向上”：在递归求高度的过程中，顺便检查是否平衡。如果子树不平衡，直接返回 -1 作为信号；如果平衡，返回真实高度。这样每个节点只需要访问一次，时间复杂度 O(n)。
这里的关键设计是：返回值不再单纯是“高度”，而是“高度或 -1 这个特殊标记”。我管这种写法叫“返回值带哨兵”。它避免了你写一个额外布尔变量去记录全局状态，因为二叉树的递归天然是自底向上的，父节点必须等子节点算完才能判断自己，所以把状态放在返回值里最干净。
实现时要注意的是，-1 这个特殊值不能和真实高度混淆。判断条件要写成：
int leftHeight = getHeight(root->left); int rightHeight = getHeight(root->right); if (leftHeight == -1 || rightHeight == -1) return -1; if (abs(leftHeight - rightHeight) > 1) return -1; return max(leftHeight, rightHeight) + 1;2.2 力扣257：路径收集的“回溯感”
257 要求返回所有从根节点到叶子节点的路径，输出格式是字符串数组，比如["1->2->5", "1->3"]。
这道题让我第一次意识到“递归与回溯”是绑定在一起的。如果你想在递归过程中维护一个路径，那么在往下走之前把节点加进去，往上返回时再把这个节点拿出来，这就是回溯。
我最初写的时候犯过一个特别典型的错：把路径作为字符串直接拼接向下传。比如定义string path，然后用path + "->" + to_string(root->val)往下传。这样写能过，因为字符串是按值传的，天然带有回溯效果。但我觉得这样不够“硬核”，因为一旦遇到“你不仅要路径，还要路径对应的某些累计值”这类衍生题，字符串拼接的写法会非常受限。
我倾向用容器记录路径节点，顺序是：
- 把当前节点加入
path容器； - 判断当前节点是不是叶子（左右都为空），是的话把容器内容组装成字符串；
- 不是叶子就递归处理左右孩子；
- 递归回来之后，把当前节点从
path中弹出。
弹出操作就是回溯的体现，也是很多新手容易漏的一步。漏掉会怎样？路径会越攒越长，最后输出的路径全都是根到某个深节点的超长路径。这个 bug 特别隐蔽，因为小树最多两三层的样例根本测不出来。
还有一点细节：拼接路径字符串时，注意区分第一个节点，不要出现->1这种开头。我是先拼第一个值，再循环拼后续的->x。
2.3 力扣404：左叶子的判定陷阱
404 的题目很直白：计算所有左叶子之和。难点不在“求和”，而在“什么算左叶子”。
左叶子必须同时满足两个条件：
- 它是它父节点的左孩子；
- 它本身没有左孩子，也没有右孩子。
很多第一反应是：在递归时判断root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr，如果成立，就把root->left->val加进去。这个方向是对的，而且我建议就用这种“站在父节点角度看左孩子”的思路，而不是尝试在递归参数里传一个布尔标记表示我是不是左孩子。
为什么不用布尔标记？因为那样需要额外参数，而且空指针的处理会更绕。站在父节点视角，代码直观，逻辑清晰，只需要判断一次就够：
int sumOfLeftLeaves(TreeNode* root) { if (!root) return 0; int sum = 0; if (root->left && !root->left->left && !root->left->right) { sum += root->left->val; } sum += sumOfLeftLeaves(root->left); sum += sumOfLeftLeaves(root->right); return sum; }这个写法有个很容易被忽略的细节：当root->left本身就是左叶子时，我把它加进了 sum，但是我在递归处理root->left时并不会重复加它，因为root->left作为子树的根，它的左右孩子都不存在，函数直接返回 0。所以这题不会重复计算。
还有一个小坑：题目给的是空树时和为 0。我的递归出口if (!root) return 0;天然覆盖了这种情况。但如果你的终止条件只写了if (root == nullptr) return 0;，在只有一个根节点的树上，根节点本身不算左叶子，那也是 0，两个写法都能处理。
2.4 力扣222：完全二叉树的位运算思维
222 是这四道题里最需要“数学思维”的一道。题目是给一棵完全二叉树，求节点个数。
最简单的解法是一个 O(n) 的遍历，任何遍历方式都能数出来。但题解里更妙的一版利用了完全二叉树的性质：
- 如果一棵子树是满二叉树，那么它的节点数是
2^height - 1； - 对根节点，先算左子树最左链深度
leftDepth，再算右子树最左链深度rightDepth。
如果leftDepth == rightDepth，说明左子树是一棵满二叉树，左子树节点数可以直接用公式算出来，再加上根节点 1 个，然后递归去算右子树节点数即可。
如果leftDepth != rightDepth，则说明右子树是满二叉树，右子树节点数用公式算，递归去算左子树。
这个递归的时间复杂度是 O(log² n)，因为每一层递归都要走一次“求最左深度”的流程，而递归深度最多是 log n，每一步求深度也是 O(log n)。
我第一次看到这个解法时，最大的认知升级是：二叉树不一定非要“全部遍历”，你可以利用树的特殊结构跳过一部分完全没有必要访问的子树。这种“能批量算就算”的思路，在后面处理很多数据结构问题时都很有用。
3. 完整代码与时间复杂度对比
3.1 C++参考实现（方便直接对照提交）
力扣110 平衡二叉树
class Solution { public: bool isBalanced(TreeNode* root) { return getHeight(root) != -1; } int getHeight(TreeNode* node) { if (!node) 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; } };力扣257 二叉树的所有路径
class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; vector<int> path; if (!root) return result; dfs(root, path, result); return result; } void dfs(TreeNode* node, vector<int>& path, vector<string>& result) { path.push_back(node->val); if (!node->left && !node->right) { string s; for (int i = 0; i < path.size(); i++) { if (i != 0) s += "->"; s += to_string(path[i]); } result.push_back(s); } else { if (node->left) dfs(node->left, path, result); if (node->right) dfs(node->right, path, result); } path.pop_back(); } };力扣404 左叶子之和
class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (!root) return 0; int sum = 0; if (root->left && !root->left->left && !root->left->right) { sum += root->left->val; } return sum + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right); } };力扣222 完全二叉树的节点个数
class Solution { public: int countNodes(TreeNode* root) { if (!root) return 0; int leftDepth = 0, rightDepth = 0; TreeNode* left = root->left; TreeNode* right = root->right; while (left) { leftDepth++; left = left->left; } while (right) { rightDepth++; right = right->left; } if (leftDepth == rightDepth) { return (1 << (leftDepth + 1)) - 1 + countNodes(root->right); } else { return (1 << (rightDepth + 1)) - 1 + countNodes(root->left); } } };这里解释一下 222 代码里的公式：如果左子树深度等于右子树深度，则左子树是满二叉树，且满二叉树高度为leftDepth + 1（从根到叶子层数），节点数为2^(leftDepth+1) - 1。这个数包含了左子树全部节点，加上根节点 1 个，再递归处理右子树。注意我没有给根节点单独加 1，因为2^(h+1) - 1已经包含了根节点本身。同理，另一种情况算的是右子树是满时的节点数。
3.2 复杂度与写法对比表
| 题目 | 遍历方向 | 时间复杂度 | 空间复杂度 | 关键技巧 |
|---|---|---|---|---|
| 110 平衡二叉树 | 自底向上 | O(n) | O(n) 递归栈 | 返回值兼做标记 |
| 257 二叉树路径 | 前序 | O(n * L) L为路径平均长度 | O(n) 递归栈 + 路径容器 | 回溯弹出 |
| 404 左叶子之和 | 任意序 | O(n) | O(n) 递归栈 | 父节点视角判定 |
| 222 完全二叉树节点 | 分治 | O(log² n) | O(log n) 递归栈 | 满二叉树公式剪枝 |
看这张表就能发现，第15天这组题基本覆盖了二叉树递归的几种常见“动作”：比较、收集路径、条件累加、数学剪枝。这些动作组合起来，就是你后面刷二叉树进阶题的基础招式。
4. 这组题最容易踩的坑
4.1 递归返回值与“全局哨兵”混用
110 题里我用 -1 当特殊标记，但有些同学会在返回值之外再维护一个全局的bool balance，然后让递归函数返回高度。这样写也能AC，但有一个隐患：递归函数一旦变复杂，你很容易忘记在某些分支更新全局变量，导致返回值正常但全局状态被漏判。
我的建议很简单：能用返回值表达状态，就不要用外部变量。原因有两个：一是返回值是天然自带回溯效果的，每个递归栈帧都有自己的返回路径，互不干扰；二是全局变量在并发或多次调用场景下要手动重置，容易产生脏数据。
4.2 路径题的重复追加与回溯遗漏
257 题我见过太多人卡在了“结果路径重复”上。典型错误是把当前节点推进去后，在处理完左孩子递归之后没有弹出，导致右孩子递归时路径容器里多了一个节点。
有个自查技巧：在递归函数入口处打印一下当前容器里的路径，再打印一下当前处理到的节点，一眼就能看出容器元素是不是只增不减。如果发现容器长度超过了树高，肯定是回溯没写好。
另一个小坑是字符串拼接效率。如果每次递归都重新拼接一个字符串往下传，时间复杂度会从 O(n) 恶化到 O(n²) 级别，因为每个节点都要复制一份完整的路径字符串。虽然力扣上小数据量看不出差别，但最好从一开始就用容器+回溯的习惯，遇到大数据也稳。
4.3 求“左叶子”时的空指针判断顺序
404 题最经典的报错是root->left->left访问了空指针。比如你在判断root->left是否存在后就觉得万事大吉，但root->left的左右子树可能有一个是空的。所以正确的判断条件是：
root->left && !root->left->left && !root->left->right这里每一个条件缺一不可。省略!root->left->left会导致把“有右孩子但不是左叶子”的节点也算进去；省略root->left会在空指针上直接段错误。
我还见过一种写法是把判断逻辑放进递归到左孩子时判断“我是不是左孩子”，需要额外传 parent 或 isLeft 参数。这种写法我强烈不建议。它会多一层判断，而且你得小心在递归到根节点时是特殊情况。站在父节点判断，是这道题代码量最少、最不容易错的方案。
4.4 222 题的位运算优先级与边界值
222 题的代码里(1 << (leftDepth + 1)) - 1很容易出错的地方是：括号漏掉、优先级理解错误、或者当leftDepth + 1接近 31 时左移溢出。题目给的数据范围一般不会走到那种极端，但写代码时还是加上括号，避免机器解析优先级和你预期不一致。
另外，有些同学在写递归时把“返回左子树节点数 + 右子树节点数 + 1”当成默认做法，这没错，但这完全没利用完全二叉树的性质，复杂度是 O(n)。如果你是在面试中遇到这题，建议两种解法都提一下：先讲朴素遍历，再抛优化思路，这比只扔一个 O(n) 的做法更能体现你对数据结构的理解。
5. 个人体会与下一步计划
这四道题刷下来，我最明显的感受是：二叉树题目的“模型感”开始成型了。所谓模型感，就是你看到一棵树，不再只是看到一个对象结构，而是能自动联想到“我要向子节点要什么、父节点怎么用”。
以前我刷题喜欢追求“代码最短”，后来发现这是假效率。真正的高效是“代码语义清晰”。比如 110 题的 -1 哨兵，牺牲了一点“纯数学美感”，但换来的是“任何人一看就懂这是非法状态”，这才是有价值的写法。404 题也一样，站在父节点判断左叶子，少绕了一圈弯，正确率肉眼可见地提高了。
下一步我打算继续刷二叉树的“构造类”题目，就是那种给你前序中序让你重建二叉树、或者给你序列化字符串还原树结构的题。因为第15天解决了“怎么遍历、怎么取数”的问题，后面的构造题才会真正考验“怎么在递归中切片”。到那时，今天养成的“返回值设计 + 回溯容器维护”这两个习惯，会直接派上大用场。
还有一个很实用的心得想分享给正在刷题的朋友：遇到一组题，不要只做完就翻篇。试着把每道题的解法抽象成一句话。比如这一轮，我的四句话是：用高度兼做平衡标记、用容器回溯拿路径、站在父节点判断左叶子、用满二叉树公式剪枝。等下次遇到新题，你的大脑会自动检索这些“知识卡片”，比重新推演一遍快得多。
