企业官网建设流程全解析

1. 开篇：二叉树刷题，别只盯着“会做”，要盯“会讲”

老规矩，先看今天这四道题：110. 平衡二叉树，404. 左叶子之和，257. 二叉树的所有路径，222. 完全二叉树的节点个数。放在一起刷，并不是因为它们在 LeetCode 上编号相邻，而是因为它们背后藏着一根非常清晰的线索：递归的返回值设计。

说实话，很多同学二叉树刷到一百多题，卡住的不是遍历框架，而是“函数到底该返回什么”。返回布尔值？返回整数？返回字符串？返回节点本身？同一个问题，换一种问法，返回值就得换一套设计。今天这四题，正好覆盖了四种典型的返回值类型：布尔、整数、字符串、整数（但用的是完全二叉树的性质）。一题一题啃下来，你会对“递归函数签名怎么定”这件事形成肌肉记忆。

这一篇我打算换个讲法：不按题号顺序讲，而是按“递归的返回类型”重新分组。先讲思路，再给可运行代码，最后把我实际提交时踩过的坑和调试技巧一起交代清楚。适合刷题进度在二叉树阶段、想系统整理递归套路的人。

2. 四道题的全局视图：它们到底在考什么

开始逐题拆之前，先把全景铺开。这四道题如果只是孤立地刷，你很难感受到它们之间的联系，但放在一起看，其实就是一道递进题组。

从遍历顺序上看，110 是标准后序遍历，404 是中序/前序辅助，257 是前序遍历路径记录，222 则是利用完全二叉树性质做二分计数。四种题型的遍历方式正好错开，刷完等于把三种基本遍历加一种性质优化全部过了一遍。

而从返回值设计上看，这四题又恰好构成了一个递进关系：先会返回布尔值（110），再会返回整数累加（404），然后会返回字符串路径（257），最后是返回整数计数并带上性质优化（222）。掌握了这四条路，二叉树递归题里最常见的返回值类型你就见齐了。

还有一个隐藏考点值得单独拎出来说：220 和 404 都涉及“在递归过程中如何携带额外状态”。110 需要同时返回高度和平衡状态，404 需要判断“当前节点是不是父亲的左孩子”，这种“一函数多用途”“父节点视角解题”的技巧，是二叉树进阶题的敲门砖。

3. 先啃第一块硬骨头：平衡二叉树的布尔返回设计

3.1 什么是平衡二叉树？先别急着递归

平衡二叉树的定义很朴素：空树是平衡的，非空树要求左右子树高度差不超过 1，且左右子树自身也都是平衡二叉树。

注意“自身也都是平衡的”这个条件，它天然指向递归。因为判断一棵树是否平衡，光看根节点左右子树的高度差还不够，必须递归地检查每一个子树。换句话说，这是一道“每个节点都要判断”的题。

我见过不少同学第一次做这题时，写出来的代码是这样的逻辑：写一个求高度的函数，然后递归判断左右子树是否平衡，在递归里反复调用求高度函数。这样能过，但时间复杂度是 O(n²)，因为每个节点都要往下扫一遍高度。

正确的做法是在递归过程中同时带回两个信息：子树是否平衡、子树的高度。但问题来了：一个函数怎么同时返回两个值？这里就有两条经典路线。

3.2 方案一：用自定义返回值或全局变量

第一种做法是用一个自定义类或者数组包装两个信息。比如 Java 里定义一个内部类ReturnNode，里面放height和isBalanced两个字段，递归返回这个对象。这种做法结构清晰，但代码量偏大。C++ 里也可以返回pair<bool, int>，Python 里可以直接返回元组(is_balanced, height)。

这种做法没什么毛病，但我个人在实际刷题时更推荐第二种，因为代码更短、提交更爽。

3.3 方案二：用 -1 标记不平衡（强烈推荐）

第二种做法是很多题解里都有的经典写法，也是我现在最推荐你掌握的：把“高度”作为返回值，但用 -1 表示“当前子树不平衡”。

核心逻辑是这样的：

1. 递归函数返回“当前子树的高度”。
2. 如果发现左右子树有任何一个返回了 -1，说明那棵子树已经不平衡了，直接返回 -1。
3. 如果左右子树都平衡，但高度差大于 1，说明当前节点不平衡，返回 -1。
4. 否则返回左右子树最大高度 + 1。

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: def height(node): if not node: return 0 left_h = height(node.left) if left_h == -1: return -1 right_h = height(node.right) if right_h == -1: return -1 if abs(left_h - right_h) > 1: return -1 return max(left_h, right_h) + 1 return height(root) != -1

这段代码我第一次写的时候，有两点体会特别深。

第一点是**“剪枝”的效果**。一旦左子树返回了 -1，整个函数立刻返回，右子树根本不会再被遍历。这个特性在保存代码里体现为if left_h == -1: return -1这一行。别小看这行，它的存在让这题的实际运行时间从 O(n²) 降到了 O(n)，因为每个节点最多被访问一次。

第二点是**“高度和平衡状态的互相纠缠”**。-1 同时肩负着“高度值为 -1”和“标记不平衡”两个语义，这看起来有点脏，但正是这种“用一个哨兵值携带额外状态”的思想，让代码量大幅缩减。很多面试官其实就吃这一套，你如果能主动解释“为什么选 -1 而不是 -2”，会加分不少。

这里我实际跑过的几个用例可以给你参考：

输入: root = [3,9,20,null,null,15,7] 输出: true 解释: 节点3的左子树高度1，右子树高度2，差为1，平衡 输入: root = [1,2,2,3,3,null,null,4,4] 输出: false 解释: 节点2的左子树高度2，右子树高度0，差为2，不平衡

3.4 平衡二叉树的两个常见踩坑点

坑一：只判断根节点左右子树高度差，不递归检查所有节点。这是最常见的错误。比如[1,2,2,3,3,4,4]这种结构，根节点左右子树高度分别为 3 和 2，差为 1，看起来平衡，但左子树的内部节点已经不平衡了。只判断根节点一定会误判。

坑二：把 -1 和 0 的语义混淆。空节点的高度是 0，这个不能改。如果你用 -1 表示空节点，那在计算差值时就会出错，因为空节点高度应该参与运算（左子树为空时，它的“高度”就是 0，表示没有子树）。我之前调试时遇到过返回结果全是 false 的情况，最后定位就是这个问题。

4. 再看左叶子之和：怎么把一个“间接条件”翻译成代码

4.1 左叶子到底怎么定义？这题一半的难点在理解题面上

404. 左叶子之和这道题，题目描述几秒钟就能读完，但“左叶子”这三个字的定义里藏着一个大坑。

叶子：左右孩子都为空的节点。

左叶子：它是它父亲的左孩子，并且它自己是一个叶子节点。

看到没有，关键在于“它是它父亲的左孩子”。这意味着：你不能只站在叶子节点本身的视角去判断“我是不是左叶子”，因为叶子节点不知道自己在父亲的哪一边。你必须站在父节点的视角去判断：“我的左孩子是否存在，且它是不是叶子节点”。

这个视角转换，是这道题真正的考点，也是递归题里很经典的一种思维方式转换。

我见过很多同学一上来就写if node.left and not node.left.left and not node.left.right，这就是正确的方向，但顺序不对，容易漏。更稳的办法是在递归函数开头就处理这种“父节点视角”的判断。

4.2 递归写法的核心逻辑与代码

思路是这样：递归遍历整棵树，每当遇到一个节点，就检查它是否有左孩子，且左孩子是否有孩子（没有就是叶子）。如果满足，累加这个左孩子的值；然后继续递归去右边找。

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

写这段代码时有一个细节值得琢磨：递归左子树时，会不会把左子树里已有的左叶子重复计算？答案是不会，因为每次递归都会重新走一遍“左孩子判断”，而根节点的左孩子如果是叶子，它就没有子节点，递归在它那里会直接返回 0，不会重复累加。

这段代码的时间复杂度是 O(n)，空间复杂度是 O(height)，在最坏情况（链状树）下高度等于节点数，递归栈会变成 O(n)。

4.3 用迭代法怎么做？前序遍历的另一种打开方式

刷题不能只会递归，迭代法有时候在面试里能救你一命，因为有些面试官会问“递归改迭代怎么改”。左叶子之和的迭代法用栈做前序遍历就能解决。

class Solution: def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int: if not root: return 0 stack = [root] total = 0 while stack: node = stack.pop() # 左叶子判断 if node.left and not node.left.left and not node.left.right: total += node.left.val if node.right: stack.append(node.right) if node.left: stack.append(node.left) return total

这里比较隐蔽的一个点在于：你把右孩子先压栈还是左孩子先压栈，不影响结果，但会影响遍历顺序。前序遍历需要先处理当前节点再处理子节点，而栈是后进先出，所以你要想先处理左子树，就得把右孩子先压进去。这个细节在改写成迭代时最容易出错，建议你自己手动推一遍。

4.4 这题容易踩的坑：直接把所有左节点的值加起来

说实话，我第一次做这题的时候，想的是“遍历所有节点，如果是左孩子就累加”，结果把“左孩子”和“左叶子”搞混了，返回的答案偏大。原因很简单：左孩子未必是叶子，比如一棵树的左孩子还有一个右孩子，它就不是叶子，不该被累加。

所以你要始终记住：题目要的是左叶子，不是左孩子。“叶子”这个限定词，决定了整个判断条件必须包含not node.left.left and not node.left.right这一串。

5. 二叉树的所有路径：从递归到回溯，字符串拼接的学问

5.1 为什么这道题必须用前序遍历？路径的本质决定了一切

257. 二叉树的所有路径，题目要求返回从根节点到所有叶子节点的路径。什么叫路径？从根出发，沿着父到子的方向一直走到叶子，把沿途的节点值串起来。

这个“从根出发”的特点决定了：你必须先访问根节点，再访问左右子树，也就是前序遍历。中序和后序遍历都不合适，因为路径的顺序要求是自上而下的。

这道题还有另一个隐含要求：路径之间互相独立。你走到一个叶子，记录下这条路径后，回到上一层，换一条路继续走，这个过程天然就是回溯。

所以这道题的最佳解法通常是：前序遍历 + 路径字符串传递 + 回溯。

5.2 递归解法：字符串参数和回溯两个流派

写递归解法时有两条路线：

路线 A：递归函数的参数里直接携带当前路径字符串，每次拼接后向下传递。

class Solution: def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]: result = [] def dfs(node, path): if not node: return # 拼接当前节点到路径 if path: path += "->" + str(node.val) else: path = str(node.val) # 叶子节点，记录路径 if not node.left and not node.right: result.append(path) return dfs(node.left, path) dfs(node.right, path) dfs(root, "") return result

路线 B：用一个共享的路径列表，回溯时弹出末尾节点。

class Solution: def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]: result = [] def dfs(node, path): if not node: return path.append(str(node.val)) if not node.left and not node.right: result.append("->".join(path)) else: dfs(node.left, path) dfs(node.right, path) # 回溯：移除当前节点 path.pop() dfs(root, []) return result

这两条路线我实际写下来，路线 A 更简洁，路线 B 更贴近“回溯”的本质。面试时如果你先写路线 A，可以补充一句“如果面试官想要回溯的经典版本，我也可以改”，然后过渡到路线 B。这种展示方式比只背一种写法更能体现你对递归和回溯的理解深度。

路线 A 的本质是利用字符串的不可变性——每次拼接后产生一个新的字符串，作为参数传下去，这样天然就避免了“需要恢复现场”的问题。它不需要显式回溯，因为每个递归分支拿到的是独立的字符串副本。

路线 B 则恰恰相反，它把路径节点存在一个共享列表里，递归返回时必须手动弹出节点，否则会污染下一个分支的路径。这就是回溯的“恢复现场”。

5.3 迭代解法：栈里存的不只有节点，还有路径

如果面试官接着问“递归改迭代”，这道题也有很漂亮的迭代解法。关键思路是你得在栈里同时存“节点”和“到该节点的路径字符串”两样东西。

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

这里用元组(node, path)作为栈元素，每压入一个子节点，就同时压入从根到该子节点的完整路径字符串。这样每个栈元素自带路径信息，天然避免了回溯。这个思路我在写代码时觉得特别巧妙，本质上是用元组把“递归函数的参数”显式地搬到了栈里。

5.4 这题容易踩的坑：根节点路径的起始格式

最简单的坑：空树直接返回空列表而不是返回包含空字符串的列表。

容易忽略的坑：根节点本身是叶子时，路径就是它本身，不应该出现"1->"这种尾巴。我一开始写的时候在“拼接箭头”的逻辑上吃了亏——如果判断是否为空来决定加不加箭头，比直接无脑拼接再切片干净得多。

还有一个隐藏得很深的坑：当树只有一个根节点时，递归和迭代两条路线的表现不同。递归路线 A 中，if path:判断为空，直接赋值不拼接，所以能正确处理；但如果你写的递归是“无论什么情况都先拼接箭头再截断”，就会在根节点这里多出一个箭头。建议你写完后直接测root = [1]这个用例。

6. 完全二叉树的节点个数：巧用性质，比暴力快一大截

6.1 为什么不能用普通二叉树的数法？它能过，但不够酷

如果只追求“能过”，这题最朴素的做法是遍历一遍数节点：

class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: if not root: return 0 return 1 + self.countNodes(root.left) + self.countNodes(root.right)

这能过，时间复杂度 O(n)。但注意题目标签是“中等”，如果只用这种方法，你等于错过了一半的考点。

另一半考点藏在题目条件里：完全二叉树。完全二叉树的特点是：除了最后一层，所有层都是满的，最后一层的节点都靠左排列。利用这个性质，我们可以做到 O(log² n) 的时间复杂度，这才是“中等题”想考的东西。

6.2 满二叉树公式和完全二叉树的完美配合

先回顾一个基础知识：一棵满二叉树（所有层都满），如果高度为 h，节点总数是 2^h - 1。

完全二叉树天然可以“拆”成若干个满二叉树的和。具体策略如下：

数一下当前节点左子树的高度和右子树的高度。

• 如果左子树高度 == 右子树高度，说明左子树是满二叉树。左子树的节点数可以直接用公式算出来，右子树继续递归。
• 如果左子树高度 > 右子树高度，说明右子树是满二叉树。右子树的节点数直接用公式算，左子树继续递归。

重复这个过程，每个递归层都会砍掉一半节点用公式直接算，所以递归深度是 O(log n)，每次递归都要数一次高度又是 O(log n)，总复杂度 O(log² n)。

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: # 左子树满，左子树节点数 = 2^left_depth - 1，加上根 = 2^left_depth return (1 << left_depth) + self.countNodes(root.right) else: # 右子树满，右子树节点数 = 2^right_depth - 1，加上根 = 2^right_depth return (1 << right_depth) + self.countNodes(root.left)

这里有一个非常漂亮的位运算技巧：1 << left_depth就是 2 的 left_depth 次方。因为满二叉树的节点总数是 2^h - 1，加上根节点就是 2^h，所以返回式里直接用1 << left_depth，少了一次加减。

6.3 为什么判断左子树和右子树高度可以决定左右哪边是满的？

这是整道题最核心的逻辑，值得单独讲讲。对于完全二叉树，如果一个节点的左子树和右子树高度相等，说明左子树一定已经填满了（最后一层节点延伸到左子树满了），右子树可能没满；如果左子树高度比右子树高度大 1，说明左子树没满，而右子树一定满了（因为完全二叉树最后一层节点靠左，右子树的高度会少一层）。

翻译成人话：

• 左右等高的场景，左子树是满的 → 左子树直接用公式。
• 左比右高一层的场景，右子树是满的 → 右子树直接用公式。

有同学可能困惑：为什么左比右高一层的场景右子树一定是满的？因为完全二叉树的填充顺序是从左到右、从上到下。如果右子树都开始有节点了，那么右子树这一层已经填满，右子树内部更不可能出现空缺。这个性质是完全二叉树独有的，普通二叉树完全不具备。

6.4 这题的写法和验证对比

我自己把两种解法都跑过，对比一下：

在普通规模的测试用例下，两种写法运行时间差距不大，但如果你手头有一个大规模完全二叉树，公式法的优势就出来了。而且面试官看到你能敏锐地利用题目条件做优化，通常会很欣赏。

这里补充一个容易踩的坑：计算高度时千万不要用递归求左右子树的最大深度，因为在完全二叉树里，一路向左走就能稳拿到根到最左叶子的层数，即整棵树的高度。如果用了通用的递归高度计算，复杂度会退化。

关于“一路向左即可得到高度”的解释：完全二叉树的叶子节点全部靠左排列，树的高度就是根节点到最左叶子节点的路径长度，所以 count 时一直往左走到底即可。

7. 从四道题提炼一套通用的递归设计方法论

刷完这四道题，如果你只记住了代码，那下次换个马甲你大概率还是不会。真正值得带走的是下面这套方法论，我总结成四个问题，每做一道树的递归题都照这个顺序问自己。

7.1 问题一：递归函数的返回值应该是什么？

这是最核心的问题，答案直接决定代码结构。

• 需要判断真假 → 返回布尔值（110 平衡二叉树）
• 需要累加数值 → 返回整数（404 左叶子之和、222 节点个数）
• 需要记录路径 → 返回字符串或字符串列表（257 所有路径）
• 需要找某个节点 → 返回节点指针（比如最近公共祖先类题目）

如果一个函数需要同时返回多个信息，优先考虑“用一个哨兵值合并”还是“用一个元组/结构体包装”。我的经验是：能合并就合并（比如 -1 标记法），合并不了再用元组。

7.2 问题二：递归的终止条件是什么？

树的递归终止条件通常有三种：

• 空节点返回基础值（0、空字符串、空列表等）
• 叶子节点做特殊处理（记录路径、累加值）
• 不满足条件的节点提前返回（比如平衡二叉树遇到 -1 直接返回）

这三种终止条件对应不同的代码风格。我习惯把“空节点”的终止条件放在递归入口最前面，统一处理，这样不用在遍历父节点时判断孩子是否为空。

7.3 问题三：当前节点要做什么？还是当前节点要做判断？

这是对照 404 和 257 两题最容易混淆的地方。

• 404 需要的是父节点视角的判断：我不能判断“我是左叶子吗”，只能判断“我的左孩子是左叶子吗”。
• 257 需要的是当前节点视角的记录：我走到哪，就把路径记录到哪。

这两种视角的差异，直接决定了递归逻辑是放在“遍历孩子之前”还是“遍历孩子时判断条件”。做题卡住时，想一想你现在是站在哪个视角说话。

7.4 问题四：递归需不需要“恢复现场”？

如果递归参数携带的是不可变数据（字符串、元组、整数），天然不用恢复现场。如果递归用的是共享可变对象（列表、集合、全局变量），必须手动恢复。

判断标准很简单：每个递归分支之间会不会互相污染数据？会污染就要回溯，不会污染就可以直接用参数传递。257 题的路线 A 和路线 B 正好演示了这两种情况，建议把两个版本都背下来，理解它们之间的取舍差异。

8. 实操过程记录：我提交时踩的坑和调试技巧

最后这部分是实战记录，把我前几天刷这组题时真实遇到的几个问题、排查过程和最终解法都整理成速查表，你可以直接拿来做避坑参考。

8.1 常见问题速查表

8.2 一个小技巧：用打印法排查递归逻辑

调试树的递归题，特别是这四道题，我强烈建议你在关键节点加临时的打印语句，直观看到递归的进出顺序。

举一个实际的例子。我在写 257 时，路线 B 老是出现路径错乱，就是在递归回溯后没有 pop 干净。排查方式是在dfs的入口和出口各加一行打印：

def dfs(node, path): print("进入:", node.val, "当前路径:", path) path.append(str(node.val)) if not node.left and not node.right: result.append("->".join(path)) else: dfs(node.left, path) dfs(node.right, path) path.pop() print("退出:", node.val, "当前路径:", path)

打印出来的结果会告诉你：每次退出递归时，path 是否被正确“还原”到了进入之前的状态。如果退出时 path 里残留了节点，说明 pop 位置放错了，或者某些分支提前 return 而没执行到 pop。

8.3 关于“刷完题要不要背代码”的实话

我一直觉得，刷 LeetCode 的终极目标不是把题背下来，而是形成一种“看到题目就能迅速归类到某个套路”的条件反射。今天这四道题就是一个很好的训练场：

• 看到“高度差”关键词 → 想到后序遍历 + 返回高度
• 看到“左叶子”关键词 → 想到父节点视角判断
• 看到“所有路径”关键词 → 想到前序遍历 + 字符串拼接或回溯
• 看到“完全二叉树 + 节点个数”关键词 → 想到满二叉树公式 + 位运算

这套“关键词 → 套路”的映射，比背十道题的代码更有价值。等你做到哪一天，拿到一道新二叉树题能在一分钟内说出“用什么遍历、返回值设计成什么、要不要回溯”，你的二叉树就算真正入门了。

拿今天这四道题回头看，110 是返回值设计的入门题，404 是视角转换的典型题，257 是路径记录与回溯的分水岭题，222 是性质应用的进阶题。把这四类题型练到肌肉记忆，下一阶段面对二叉树的中等偏难题（路径总和系列、最近公共祖先系列）会轻松很多。