企业官网建设流程全解析

刷到代码随想录算法训练营第15天，正好是我感觉自己二叉树基础题开始“不够用”的时候。这一天安排的四道力扣题——110平衡二叉树、257二叉树的所有路径、404左叶子之和、222完全二叉树的节点个数——把递归里最容易含糊的几个点全给点了一遍：返回值怎么设计、回溯什么时候发生、叶子节点的定义怎么抠、完全二叉树性质如何变成复杂度优势。如果你正跟着训练营在刷，或者二叉树基础题已经过完、想在递归和回溯上再扎实一点的，这篇可以当一份很干的刷题笔记用。

1. 第15天任务拆解：四道题到底在练什么

1.1 四道题的定位与难度梯度

这四道题按题号排是110、257、404、222，但按内容分，其实覆盖了二叉树递归的四种典型流派。我先把它们的定位和难度体感列成一张表，后面再逐个拆。

单看每一道题都是二叉树的遍历，但把它们放在同一天练，训练营的意图其实很明确：逼你把递归函数的职责想清楚。110要把子树的高度“送上来”，257要把路径上的节点“带下去”，404要判断当前节点和左孩子的关系，222则是利用整棵树的结构性质直接跳过一整棵子树的遍历。四种递归节奏放在一起，比连续刷十道同类题更能刺激思考。

这四道题还有一个共同点：都可以用暴力写法AC。110可以每个节点重新求高度，257可以用字符串传值免去回溯，404可以加isLeft参数，222可以层序遍历计数。但暴力写法往往正好绕开了考点，这也是为什么很多人AC了还是觉得没学到东西。

1.2 我推荐的刷题顺序与节奏

我实际刷的时候没有按题号来，而是按难度递增：先做404左叶子之和，因为它最简单，用来热手很合适；再做110平衡二叉树，巩固后序遍历；然后做257所有路径，这一题要花时间把回溯想透；最后做222完全二叉树的节点个数，它最硬核，需要完全二叉树的性质做剪枝。

按这个顺序，每道题的心智负担是慢慢加重的。如果你一上来就啃222，很容易被位运算和满二叉树性质劝退。时间预算上，404大约15分钟，110大约25分钟，257大约40分钟，222大约45分钟，整体两小时上下。超时特别正常，尤其是257第一次接触回溯的时候，卡一个小时不丢人。

每道题我都要求自己先不看题解想十分钟，想不出来再看答案，然后关掉答案手写一遍。这个流程对“刷完就忘”非常有效，因为你看懂答案只是输入，自己重新写一遍才是输出。

2. 逐题拆解：从题意到递归设计的完整思路

2.1 力扣110 平衡二叉树：递归返回值比你想的更重要

题目给一棵二叉树，判断它是不是高度平衡的二叉树。平衡的定义很关键：每个节点的左右子树高度差不超过1。注意是每个节点，不是只有根节点。

为什么不能用先序遍历？因为判断一个节点是否平衡，需要它的左右子树高度，而高度只能自底向上算，天然就是后序遍历才能拿到的信息。先序遍历只能从上往下判断根节点，根本不知道子树内部平不平衡。

递归设计思路是这样：写一个getHeight(node)函数，返回以node为根的子树高度，如果发现这棵子树已经不平衡，就返回-1作为哨兵。空节点高度记0。求左子树高度，如果已经是-1直接返回-1，说明左子树不平衡，整棵树不可能平衡，可以提前剪枝；右子树同理。最后比较左右高度差，大于1就返回-1，否则返回max(left, right) + 1。

为什么用-1而不是返回bool，再单独搞一个全局变量记录高度？因为递归返回值在每一层是独立的，全局变量会被层层覆盖，父节点根本拿不到子树的真实高度。用一个int同时承载“这棵子树多高”和“是否平衡”两个信息，是最内聚的写法。很多初学者写110跑不对，就是掉进了“递归里想用bool又想传高度”的坑。

举个例子：根节点1，左子树2，2的左孩子4，没有右子树。单看根节点，左子树高度2，右子树高度0，差为2，已经不平衡。但即使根节点左右差等于1，子树内部也可能已经差了2，所以必须后序遍历到底。这个例子说明“根节点平衡”不等于“整棵树平衡”。

2.2 力扣257 二叉树的所有路径：回溯就藏在递归的往返之间

题目要求返回所有从根节点到叶子的路径，输出形如["1->2->5", "1->3"]。解法用前序遍历，先处理当前节点，把它推进一个路径容器path里；如果当前节点是叶子，就把path转成字符串放进结果集；否则分别递归左右孩子，递归返回后要从path里把当前节点pop掉。

这个pop操作就是回溯。我习惯用一个生活类比：在岔路口用铅笔在本子上记路线，走到死路返回岔路口时，必须把刚才那条路的记录擦掉，才能继续记下一条。如果不擦，第二条路就会带着前一条路的残影，最后输出的路径全是串线。

为什么推荐用vector<int>& path而不是直接用string传值？因为string按值传递时，每次递归都会拷贝一份，旧字符串根本没被修改，隐式实现了“撤销”，但代价是让初学者误以为回溯是自动发生的。vector<int>& path是真正的共享引用，递归返回后必须手动pop_back，才能逼你关注回溯的时机和位置。

贴一个容易踩的实现细节：不要在叶子节点提前return然后指望调用处pop，这样代码里会出现两处pop、对称性很差。更稳的写法是无论叶子还是非叶子，都在递归函数末尾统一pop_back。下面这份代码是我推荐的样子。

class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; vector<int> path; if (root != nullptr) { 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) { result.push_back(pathToString(path)); } else { if (node->left) traversal(node->left, path, result); if (node->right) traversal(node->right, path, result); } path.pop_back(); } string pathToString(const vector<int>& path) { string s; for (int i = 0; i < path.size(); ++i) { if (i > 0) s += "->"; s += to_string(path[i]); } return s; } };

这个版本里，叶子节点也会走到最后的pop_back，所以递归返回时path一定恢复原状，逻辑对称、不容易漏。

2.3 力扣404 左叶子之和：在父节点上做判断才干脆

题目要求计算所有左叶子节点值的和。左叶子的定义要抠字眼：它是父节点的左孩子，并且它自己没有左右孩子。

很多人第一反应是递归遍历所有节点，遇到叶子再判断“我是不是左孩子”。但递归函数默认只拿到当前节点，并不知道自己在父节点眼里是左还是右，除非给递归函数额外传一个bool isLeft参数。这种方案能做，但代码会绕，而且容易把状态传错。

更简洁的方案是在父节点位置做判断。递归到node时检查node->left，如果它不为空，且它的左右孩子都为空，那么node->left就是一个左叶子，直接累加。然后继续递归左子树和右子树。

这里有一个必须强调的坑：不能只递归左子树就return。因为右子树内部也可能有左叶子。比如根节点只有右孩子3，右孩子3又有一个左孩子4，4就是左叶子，必须通过递归右子树才能加到。所以即使当前节点的左孩子是叶子，也要继续递归它，只不过它的左右子树都为空，递归返回0，不会重复计数。

核心代码逻辑可以浓缩成一句话：先判断“当前节点的左孩子是不是叶子”，是就加上；然后无条件递归左右子树。这个思路在代码里非常清爽。

2.4 力扣222 完全二叉树的节点个数：用满二叉树性质做剪枝

完全二叉树的标准定义是：叶子节点只能出现在最下层，并且最下层的叶子节点连续集中在左侧。求节点总数，最简单的做法是遍历整棵树，递归或层序都能过，但时间复杂度是O(N)。

这道题的进阶考点是利用完全二叉树性质做到O(logN * logN)。核心观察是满二叉树的节点数可以直接用深度算：一棵深度为d的满二叉树，节点数是2^d - 1（这里的d按“最左侧路径节点数”定义，单节点深度为1）。那么只要能判断出某棵子树是满二叉树，就不用遍历它，直接套公式。

怎么判断？写一个getDepth(node)，从node出发一路沿着左孩子走，统计最左侧路径的节点数，代价是O(logN)。对根节点分别算左子树和右子树的最左侧深度。

如果两者相等，说明左子树必然是一棵满二叉树。原因很简单：完全二叉树从左到右填充，右子树能到达同一深度，左子树不可能还缺节点。此时左子树节点数直接用2^leftDepth - 1算，根节点再加1，所以根节点的左子树加上根节点合计2^leftDepth，然后递归算右子树。

如果两者不相等，那么一定是左深度比右深度多1，并且右子树是满的。此时根节点加上右子树合计2^rightDepth，然后递归算左子树。这个性质可能反直觉，但画棵树逐层填充就能理解，完全二叉树的层内连续性决定了“右侧到达的深度”就代表这一层已经填满。

位运算要注意：1 << leftDepth就是2的leftDepth次方。在上面两个分支里，这个值表示的分别是“左子树+根”或“右子树+根”的节点数，千万不要随手再减一。我建议提交前先手推三个用例：只有根节点、根带一个左孩子、根带左右两个孩子，确保公式没写反。

3. 实操代码实现：递归三要素与四份可直接复用的代码

3.1 动手前先回答三个问题

写任何二叉树递归题，写代码前先口头回答三个问题：递归函数返回什么？终止条件是什么？单层逻辑处理什么？把这四道题对齐到这三个问题，就能得到一张非常直观的表格。

这张表填完，代码基本就是填空了。很多人写递归卡住，不是不会语法，而是没想清楚“这个函数到底要向上层返回什么信息”。110返回高度和平衡状态，222返回节点数，这两个是典型的数值型递归；257和404则是把结果放在外部的result或累加变量里，递归函数本身不返回业务值。分清楚这两种模式能少踩一半的坑。

3.2 完整实现：C++与Python对照

下面把四道题的可提交版本都贴出来。C++版默认力扣环境已经引入标准库，如果要在本地编译，110需要包含<cstdlib>或<cmath>。

110平衡二叉树的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; } };

110的Python实现：

from typing import Optional class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: def height(node): if not node: return 0 left = height(node.left) if left == -1: return -1 right = height(node.right) if right == -1: return -1 if abs(left - right) > 1: return -1 return max(left, right) + 1 return height(root) != -1

257所有路径的C++实现：

class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; vector<int> path; if (root != nullptr) { 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) { result.push_back(pathToString(path)); } else { if (node->left) traversal(node->left, path, result); if (node->right) traversal(node->right, path, result); } path.pop_back(); } string pathToString(const vector<int>& path) { string s; for (int i = 0; i < path.size(); ++i) { if (i > 0) s += "->"; s += to_string(path[i]); } return s; } };

257的Python实现，这里用字符串直接拼接，隐式实现了回溯，代码更短：

from typing import Optional, List class Solution: def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]: result = [] if not root: return result def dfs(node, path): if not node.left and not node.right: result.append(path) return if node.left: dfs(node.left, path + "->" + str(node.left.val)) if node.right: dfs(node.right, path + "->" + str(node.right.val)) dfs(root, str(root.val)) return result

404左叶子之和的C++实现：

class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root == nullptr) return 0; int sum = 0; if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr) { sum += root->left->val; } sum += sumOfLeftLeaves(root->left); sum += sumOfLeftLeaves(root->right); return sum; } };

404的Python实现：

from typing import Optional class Solution: def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int: if not root: return 0 total = 0 if root.left and not root.left.left and not root.left.right: total += root.left.val total += self.sumOfLeftLeaves(root.left) total += self.sumOfLeftLeaves(root.right) return total

222完全二叉树节点数的C++实现：

class Solution { public: int countNodes(TreeNode* root) { if (root == nullptr) return 0; int leftDepth = getDepth(root->left); int rightDepth = getDepth(root->right); if (leftDepth == rightDepth) { return (1 << leftDepth) + countNodes(root->right); } else { return (1 << rightDepth) + countNodes(root->left); } } private: int getDepth(TreeNode* node) { int depth = 0; while (node != nullptr) { ++depth; node = node->left; } return depth; } };

222的Python实现：

from typing import Optional class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: if not root: return 0 def depth(node): d = 0 while node: d += 1 node = node.left return d left_depth = depth(root.left) right_depth = depth(root.right) if left_depth == right_depth: return (1 << left_depth) + self.countNodes(root.right) return (1 << right_depth) + self.countNodes(root.left)

3.3 复杂度实测对比

写完之后一定要有复杂度意识。这道题很多人AC了但说不清复杂度，面试基本就穿帮了。

257为什么最坏是O(N^2)？因为每个叶子路径的长度和树高相关，输出结果本身的长度就有O(N * H)。C++用to_string拼字符串时还会不断拷贝，树退化成链表的时候尤其明显。不过力扣正常数据下不会触发极端情况。

222优化版的复杂度值得多说一句：每次countNodes只会递归进入其中一侧子树，但每次进去之前都要算两个getDepth，每个getDepth是沿着最左侧走，代价O(logN)，所以总体是O(logN * logN)。空间复杂度是递归深度O(logN)。在节点数接近10^9的大完全二叉树上，普通遍历要秒级，优化解法是毫秒级。

4. 容易踩的坑与调试技巧实录

4.1 返回值设计和全局变量的分工错误

110最常见的错误就是递归函数返回bool，然后在递归里试图用成员变量记录高度。这样做的结果是：递归返回后高度变量被上层覆盖，父节点根本拿不到子树真实高度，判断就全乱了。要么用哨兵int返回高度，要么额外维护高度表，前者明显更干净。

257最常见的错误是忘记pop_back，输出结果出现“1->2->5->3”这种串线路径。另一个错误版本是在叶子节点提前return，然后在调用处补一个pop，结果逻辑东一榔头西一棒子，很难查。我推荐统一在函数末尾pop，这样每个节点“推进去一次，必然弹出来一次”，对称性是最好的。

404的经典错误是把“左子树的叶子”误当成“左叶子”，只递归左子树然后return，完全丢掉右子树里的左叶子。还有人在叶子节点试图判断自己是不是左孩子，然后发现递归函数根本不知道这个信息，只能加参数绕弯。

222的经典错误是直接把完全二叉树当成满二叉树，上来就返回2^depth - 1。完全二叉树只有在每一层都满的时候才等于满二叉树，所以必须加左右深度相等的判断。另一处是位运算写反：1 << depth里的depth和“最左侧路径节点数”的定义要保持一致，我自己第一次写的时候就在相等分支里多减了一个1。

4.2 边界条件自查清单

刷完AC之后，至少用下面这些边界用例自查一遍，能过滤掉大部分隐藏问题：

• 空树：110返回true，257返回空列表，404返回0，222返回0。
• 单节点：110返回true，257输出["1"]，404是0，因为根节点不算左叶子，222是1。
• 左单链1-2-4：110应该返回false，因为节点1的左右子树高度差是2。
• 根节点只有右孩子，右孩子又有左孩子：404的左叶子之和要能算出来，这是最容易被漏掉的情况。
• 完全二叉树但不完整，比如[1,2,3,4]：222优化解法要能算出4，不能误判成满二叉树。

特别是222，建议把用例[1,2,3,4]和[1,2,3,4,5,6]都手推一遍。前一个会走“左右深度不等→右子树满”的分支，后一个会走“左右深度相等→左子树满”的分支。两个分支都验过，代码基本就稳了。

4.3 调试小技巧：打印法定位回溯误区

二叉树递归题最通用的调试手段是打印递归进入和退出的信号。以257为例，在traversal入口打印当前节点值和path大小，在pop_back之后打印退出时的path大小。如果发现退出时path大小比进入时大，说明某次递归漏了pop，输出的路径就必定串线。

110可以在getHeight里打印每个节点返回的高度，找到第一个-1出现的位置，就能快速定位是哪棵子树先不平衡，比盯着空荡荡的编译器报错强得多。

222可以在countNodes里打印leftDepth和rightDepth，观察满二叉树判断的分支是如何生效的。我调试时的习惯是先用小用例验证公式，再随机构造一个5层左右的完全二叉树，肉眼验证节点数结果。递归的问题，用打印法基本都能在几分钟内定位。

说实话，我不是那种一次就能把四道题全部通过的选手。257第一次写就忘了pop_back，多跑了几遍才把“递归返回时擦掉选择”这个动作刻进肌肉记忆。后来刷二叉搜索树、回溯子集和排列问题时，才发现训练营第15天安排的这几个题，反复在练同一件事：设计好递归的返回值，看清递归的往返时机。如果你今天刷到这四道题觉得吃力，很正常。多花一点时间把每道题用两种写法各做一遍，比草草AC四道题更有意义。