企业官网建设流程全解析

刷二叉树刷到第十三天，我最大的感受是：递归函数的调用栈一深，人就开始懵。不是不懂“递归”这两个字，而是拿到一道题不知道递归函数该返回什么、该在哪一步做处理、什么时候该回溯。代码随想录训练营第十三天的这四道题——110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和、222.完全二叉树的节点个数，刚好把这些问题全部覆盖了一遍。四道题看起来是四个独立题目，实际是一套组合拳：高度和深度的概念、先序后序各自的应用场景、回溯在递归里的位置、以及完全二叉树的数学性质。我把这四道题放在一起复盘了一遍，发现只要把几个关键点打通，很多二叉树递归题都能顺手做出来。

1. 先把“深度”和“高度”掰扯清楚，后面四道题才做得下去

这四道题里，110题是直接考平衡二叉树的，而平衡二叉树的定义依赖于“高度”。但很多人在这一步就被绕晕了，因为深度和高度这两个概念长得太像，网上的定义又各说各话。不把这个问题钉死，后面全是糊涂账。

1.1 深度是从根往下数的，高度是从叶子往上数的

我的个人建议是，记住两句话就够了：

• 深度（depth）：从根节点到当前节点经过的节点数或边数，方向是自上而下。
• 高度（height）：从当前节点到最远叶子节点经过的节点数或边数，方向是自下而上。

拿一棵最简单的三层满二叉树来看：

1 / \ 2 3 / \ \ 4 5 6

节点1的深度是1，节点2和3的深度是2，节点4、5、6的深度是3。反过来看高度，节点4、5、6作为叶子节点，高度是1；节点2的高度是2；整棵树的高度取决于根节点到最远叶子的距离，也就是3。

这里有个细节经常引起争论：深度和高度到底是按节点数算还是按边数算。LeetCode里通常用节点数来定义，也就是根节点深度为1、叶子节点高度为1。如果你在别的教材里看到根节点深度为0的写法，那就是按边算了，不影响算法思路，但写代码时初始值要对齐。

1.2 求深度用先序，求高度用后序——这不是风格偏好，是遍历顺序决定的

我见过很多人一上来就问：“求个深度而已，用哪种遍历不一样吗？”还真不一样。

求深度，是从根节点开始往下探，每走一层就把层数加一，这是典型的先序遍历场景：先处理当前节点，再去递归孩子。求高度，是先知道左右子树各自的高度，再取最大值加一得到当前节点的高度，这是典型的后序遍历场景：先递归到底层，再把结果一层层往上返。

我在训练营里学到的一个口诀是“先序往下带参数，后序往上返结果”。求深度时你往往需要一个参数记录当前层数，每层递归自己往下传；求高度时你不需要额外参数，递归函数的返回值本身就代表子树高度。

这套区分在110题里会直接体现出来。如果题目要求判断一棵树是否平衡，你要算的是每个节点的左右子树高度差，那天然就是后序遍历。很多人在110题里卡住，根本原因不是不会写递归，而是没有意识到这个题本质上是在“从下往上收集高度信息”。

2. 110.平衡二叉树：后序遍历求高度，剪枝才是灵魂

平衡二叉树的定义本身不难理解：一棵树是平衡的，当且仅当每个节点的左右子树高度差的绝对值不超过1。注意是“每个节点”，不是只看根节点。这个限定条件让很多人第一次提交的时候挂掉——只比较了根节点的左右子树高度，没有递归往下检查。

2.1 题目到底在考什么

先把题目要求翻译成人话：给定一棵二叉树，判断它是不是高度平衡的。这里的“高度平衡”就是上面说的每个节点都满足左右子树高度差不超过1。

暴力做法很容易想到：写一个求高度的函数，然后在每个节点上调用这个函数比较左右子树高度差，再递归检查左右子树。这样确实能过，但问题在于重复计算严重——求上层节点高度时把下层节点遍历了一遍，求下层节点高度时又遍历了一遍，时间复杂度是O(n log n)级别的，最坏情况下会退化到O(n^2)。

正确的做法是把求高度和判断平衡合并到一次递归里，用后序遍历一边算高度一边检查平衡性。

2.2 为什么返回-1这个“哨兵值”

后序遍历递归函数的核心设计是：返回值代表当前节点的高度。但如果当前节点的左右子树已经不平衡了，我们其实不需要再往上精确返回它的高度，只需要告诉上层“这里已经坏了”。这时候一个常用技巧是返回-1作为哨兵值。

代码我直接贴在下面，这个版本我反复写了好几遍，是目前最顺手的写法：

class Solution { public: int getHeight(TreeNode* node) { if (node == NULL) 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 1 + max(leftHeight, rightHeight); } bool isBalanced(TreeNode* root) { return getHeight(root) != -1; } };

这里有一个我一开始没想通的点：为什么在递归返回-1之前，要先检查leftHeight和rightHeight是否已经为-1？其实这是提前终止。如果左子树已经不平衡了，那当前节点和右子树的高度差已经没有继续判断的意义了，直接往上抛-1，避免无意义的递归。这个操作就是剪枝。

2.3 代码落地与三个容易翻车的地方

第一个坑：忘了检查子树是否已经不平衡。很多第一版代码会写成这样：

int leftHeight = getHeight(node->left); int rightHeight = getHeight(node->right); if (abs(leftHeight - rightHeight) > 1) return -1;

表面上看逻辑没错，但leftHeight是-1的时候，abs(-1 - rightHeight)可能恰好小于等于1，于是这个节点被误判成平衡。实际上左子树早就挂了，返回值却被吞掉了。所以必须先判断子树返回的-1，再去做高度差判断。

第二个坑：递归终止条件。空节点返回0，这个基本不会错。但如果题目定义的叶子节点高度是0，你需要相应调整终止条件的返回值。这里又回到第一节说的：深度和高度按节点数算，空节点高度为0，叶子节点高度为1，代码就是这么对应的。

第三个坑：只有根节点的树。很多人写isBalanced时习惯性判断root为空返回true，但容易漏掉只有一个节点也应该返回true的情况。上面的解法其实已经天然覆盖了：单节点树，左右子树都为空，高度差为0，getHeight返回1，不是-1，所以返回true。

时间复杂度的分析也值得记一下：每个节点只被访问一次，每次操作是常数时间的比较和绝对值运算，整体O(n)。空间复杂度主要是递归调用栈的深度，最坏情况退化成链表时是O(n)，平均情况下是O(log n)。

3. 257.二叉树的所有路径：回溯不是玄学，它是递归的“后悔药”

如果110题让你理解了后序遍历“从下往上返回结果”，那257题就是完全相反的思路：从上往下记录路径，走到叶子节点就把路径存起来，然后掉头往回走。这个掉头的过程，就是回溯。

3.1 为什么这题必须用先序

题目要求返回所有从根节点到叶子节点的路径，比如：

1 / \ 2 3 \ 5

输出是：

["1->2->5", "1->3"]

要拼出路径，你必须先拿到根节点的值，然后向左右子树扩展，所以根节点要先被处理——这就是先序遍历。中序和后序在这种场景下都不合适，因为等你处理到根节点的时候，路径已经很难拼回去了。

3.2 path.pop_back() 到底在做什么

这是我第一次刷这题时最懵的地方。路径问题的常规写法是用一个vector path来记录当前走过的节点，然后每次递归返回时，要把path末尾的节点弹出去。为什么？因为path是共享的，你从子树A回来之后，path还是之前的样子，如果不把子树A的节点弹出，进入子树B时路径就不对了。

我用一个具体的例子演示这个过程。还是上面那棵树，初始path为空，根节点1入path，path=[1]。往左孩子2走，path=[1,2]，接着往右孩子5走，path=[1,2,5]，此时5是叶子，把“1->2->5”加入结果。然后递归返回到节点2，此时就要把5弹出，path=[1,2]。再返回到根节点1，把2弹出，path=[1]。再往右孩子3走，path=[1,3]，3是叶子，加入“1->3”。

如果少了pop_back这一步，进入右子树3时path还是[1,2,5,3]，结果完全错乱。

代码是训练营里比较经典的一个版本：

class Solution { private: void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) { // 进来先push当前节点，保证叶子节点也能被记录 path.push_back(cur->val); // 到达叶子节点，拼接路径 if (cur->left == NULL && cur->right == NULL) { string sPath; for (int i = 0; i < path.size() - 1; i++) { sPath += to_string(path[i]); sPath += "->"; } sPath += to_string(path[path.size() - 1]); result.push_back(sPath); return; } if (cur->left) { traversal(cur->left, path, result); path.pop_back(); // 回溯 } if (cur->right) { traversal(cur->right, path, result); path.pop_back(); // 回溯 } } public: vector<string> binaryTreePaths(TreeNode* root) { vector<int> path; vector<string> result; if (root == NULL) return result; traversal(root, path, result); return result; } };

注意这里有个细节：path.push_back(cur->val)放在了函数开头，叶子节点返回时并没有在递归函数内部做pop_back，而是在上层递归的调用处做pop_back。这是很多教程的常规写法，只需要记住“谁调用递归，谁负责弹出”就不会乱。

如果你喜欢对称的写法，也可以在叶子节点return之前把path中的当前节点弹出，效果一样。我自己的习惯是统一采用“调用处弹出”，因为这样不需要在多个return路径上都想着弹出，容易漏。

3.3 隐藏的坑与迭代法扩展

第一个坑：递归函数里path参数的类型。如果你定义成vector path（值传递），那每次递归都会拷贝一份path，不用pop_back也不会出错，但空间开销会变大。我用引用vector &，回溯操作才有意义。第一次写的人经常在这里卡住——用了值传递，pop_back之后发现path没变，因为pop的是副本。

第二个坑：字符串拼接的耗时。每个叶子节点都要把整个path转成字符串，如果树很大，这个开销不小。LeetCode里一般规模下没问题，但如果是面试场景，可以改成从根到叶子传string而不是vector，每层递归直接拼接“val->”，这样避免了最后再遍历path数组。代际写法各有优劣，vector方式的好处是调试方便。

再给一个迭代版的思路。用栈模拟递归时，栈里不能只存节点，还要同时存这条路径对应的字符串。每次压栈时把当前的路径字符串一起压进去，弹出时就能直接得到完整路径。这个思路在遇到N叉树的所有路径问题时特别管用，因为不需要手动回溯，路径信息永远跟着当前节点走。

class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; if (root == NULL) return result; stack<pair<TreeNode*, string>> st; st.push({root, to_string(root->val)}); while (!st.empty()) { auto [node, path] = st.top(); st.pop(); if (node->left == NULL && node->right == NULL) { result.push_back(path); } if (node->right) { st.push({node->right, path + "->" + to_string(node->right->val)}); } if (node->left) { st.push({node->left, path + "->" + to_string(node->left->val)}); } } return result; } };

注意压栈顺序，因为栈是后进先出，想让左子树先处理就后压左子树。这是我每次写迭代法都会顺手检查一遍的地方，顺序错了输出结果顺序会变，虽然题目不一定要求顺序，但调试时容易造成误导。

4. 404.左叶子之和：判断条件别写在叶子身上，要去问它的父节点

这道题的通过率在一开始刷的时候经常让人意外，题目本身看起来很简单：“计算给定二叉树所有左叶子之和”。但很多人第一次提交都在一个地方栽了跟头——把“左叶子”理解成了“左子树的所有叶子节点”或者“靠左边的叶子节点”，然后开始各种排列组合判断。

4.1 左叶子的定义坑

先明确定义：一个节点是左叶子，需要同时满足两个条件：

• 它是叶子节点（左右孩子都为空）；
• 它是父节点的左孩子。

注意第二条，这个条件意味着：判断左叶子这件事，不能只看节点自己，还要知道它的父节点。你在递归遍历的过程中遇到一个叶子节点，你是不知道它是左孩子还是右孩子的，除非把方向信息传下去，或者换个角度——在父节点那里判断。

我一开始就是这么踩坑的：写一个递归函数遍历所有节点，在叶子节点时判断它是不是左边来的，结果不得不给递归函数添加一个isLeft参数。这个方案也能做，但代码不够干净。更好的思路是：在父节点那里判断“我的左孩子是不是左叶子”。

4.2 从父节点判断的递归写法

核心逻辑只有一段：

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

解释一下：midValue表示当前节点如果存在左叶子，就把这个左叶子的值加进来。例如节点3的左孩子是叶子，midValue就是叶子节点的值。然后分别递归左子树和右子树，在子树里继续找左叶子。

这里有个容易担心的点：根节点为空的处理。空节点没有左孩子，递归下去返回0，自然就排除了。

另一个容易担心的点是：如果root->left本身就是一个左叶子，那递归root->left时会不会把它再算一遍？不会。因为递归root->left时，那个叶子的左右孩子都是空，midValue是0，leftValue和rightValue也都是0，所以它本身不会被重复计入。左叶子的值只在它的父节点那一层被计数一次。

4.3 我用过的错误写法对比

再分享一个反面教材。一开始我写过下面这个版本：

int sum = 0; void dfs(TreeNode* node, bool isLeft) { if (node == NULL) return; if (node->left == NULL && node->right == NULL && isLeft) { sum += node->val; } dfs(node->left, true); dfs(node->right, false); }

这个方案也能得出正确答案，但问题在于：

• 需要维护一个额外的全局变量sum，在多线程测试或多次调用时容易出问题；
• 需要给dfs增加isLeft参数，理解成本比父节点判断法高；
• 如果题目要求返回int而不是用类成员变量，写法要再调整。

所以我最终推荐的还是父节点判断法。它完美体现了“递归函数返回子问题的解，然后合并”这种思路，和110题、222题的递归框架保持一致。一套框架打通四道题，比你每道题记一个特殊套路要省力得多。

这道题还有迭代版本，用栈模拟中序或先序遍历都可以。判断逻辑不变，只要在遍历过程中继续用“父节点看左孩子是否为左叶子”这个套路：

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

我建议新手至少把递归版写熟，迭代法作为一个参考思路去理解。因为递归版更贴近问题本质，在面试中口述思路也更顺。

5. 222.完全二叉树的节点个数：暴力解O(n)不算完，利用性质优化到O(log n × log n)

这道题最直接的解法太明显了，以至于很多人都忽略了它背后对完全二叉树性质的考察。LeetCode的提交记录里，递归一行流写法就能过，但如果你只写暴力遍历，那就失去了这道题的真正价值。

5.1 最朴素的递归版本

先给最直接的递归版，任何一个遍历都行：

class Solution { public: int countNodes(TreeNode* root) { if (root == NULL) return 0; return 1 + countNodes(root->left) + countNodes(root->right); } };

这段代码的逻辑很清楚：空节点返回0，非空节点等于自身1个加上左子树节点数加上右子树节点数。时间复杂度O(n)，因为每个节点都会被访问一次。

也可以用层序遍历逐层累加，或者先序、中序、后序任何一种遍历方式去数，本质都是O(n)。在完全二叉树这个前提下，其实我们可以做得更快。

5.2 完全二叉树的“天赐”性质

完全二叉树（Complete Binary Tree）的定义是：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最底层的节点集中在最左边若干个位置。

这个定义带来两个关键推论：

• 如果一棵完全二叉树的左右子树深度相同，那么这棵子树一定是一棵满二叉树；
• 满二叉树的节点数可以直接用公式计算：节点数 = 2^深度 - 1（这里的深度按层数/高度从1开始算）。

举个例子，高度为3的满二叉树，节点数就是2^3 - 1 = 7。

这个性质非常有用，因为满二叉树的节点数不需要递归去数，一个公式就能算出来。所以优化的方向是：每到一个节点，判断以它为根的子树是不是满二叉树，如果是，直接套公式返回；如果不是，再递归去算左右子树。

5.3 优化代码和时间复杂度推导

判断一棵子树是不是满二叉树，不需要真的数一遍所有节点。只要从当前节点出发，沿着最左路径走到底的深度，和沿着最右路径走到底的深度相等，就说明底层节点是铺满的，这棵子树是满二叉树。

代码是这样：

class Solution { public: int countNodes(TreeNode* root) { if (root == NULL) return 0; TreeNode* left = root->left; TreeNode* right = root->right; int leftDepth = 0; int rightDepth = 0; while (left) { left = left->left; leftDepth++; } while (right) { right = right->right; rightDepth++; } if (leftDepth == rightDepth) { // 以root为根的树是满二叉树，节点数为2^(深度+1) - 1 return (2 << leftDepth) - 1; } return 1 + countNodes(root->left) + countNodes(root->right); } };

注意代码里(2 << leftDepth) - 1这个表达式。当leftDepth=0时，说明以root为根的树只有一个节点，结果是(2<<0)-1=1，正确；当leftDepth=1时，说明这棵树除root外还有左右两层，即总共3个节点，结果是(2<<1)-1=3，正确；当leftDepth=2时，结果是7，也正确。它等价于2^(leftDepth+1) - 1，只是用位运算写出来更简洁。这里我不建议你为了炫技强行记这个表达式，理解成满二叉树公式就行，代码写(1 << (leftDepth + 1)) - 1也完全没问题。

时间复杂度分析是这个优化的精髓。每一层递归都会做一次向左、向右“探底”的操作，每次探底需要O(log n)时间。但注意，递归的次数不是O(n)，因为一旦遇到满二叉树子树，会直接返回公式结果。完全二叉树的递归过程中，每棵子树要么是满的，要么继续向下递归，而递归深度最多是O(log n)。所以总时间复杂度是O(log n × log n)，比O(n)低了一个量级。

我实测过这个版本在LeetCode上的运行时间，相比简单递归确实有明显提升。数据量越大、树越深，优势越明显。

5.4 这个优化对普通二叉树为什么不成立

有人可能会想：这个优化这么好，我拿它去算普通二叉树的行不行？

不行。关键在于完全二叉树保证了一条性质：如果节点左右深度相同，子树必然满。但普通二叉树没有这个保证。一个普通节点，左子树一直往左走到3层，右子树一直往右走也到3层，这不代表这棵子树所有层的节点都是满的。中间可能缺了很多节点，比如某个右孩子为空。这时候套用满二叉树公式就会算错。

这也是为什么很多算法题会特意在题目里强调“完全二叉树”，就是为了给你提供额外的数学结构，让某些计算能够跳过枚举。如果你无视这个条件，等于把这个信息扔掉了。

面试时如果问到这里，我一般还会多说一句：这个思路的本质是二分——用满二叉树的性质快速判断一条路径上有没有缺口，有缺口就继续二分，没有缺口就直接结算。和二分查找的思想是一脉相承的。

6. 四道题刷完，我对递归的三点新体会

训练营第十三天这四道题刷完之后，我回看自己前几天的代码，发现有几个很明显的进步。先把这四道题的定位再串一遍：110题教你用后序返回值表达“从下往上”的聚合信息；257题教你用先序路径加回溯表达“从上往下”的探索过程；404题教你巧妙选择判断节点——左叶子的计数放在父节点完成；222题教你利用完全二叉树的数学性质跳过重复计算。

第一点体会是：递归函数的返回值设计决定了题目的难度。110题的返回值是高度，同时用-1表达异常；257题不需要返回值，因为结果通过引用参数收集；404题返回值是左叶子之和；222题返回值是节点个数。返回值到底应该是什么，取决于你要从子问题里拿到什么信息。这比背模板重要得多。

第二点体会是：回溯的“弹栈”动作不是递归的附加品，而是递归过程的一部分。每次递归调用像一次“前进”，pop_back就是“后退”。很多题目如果只记得写traversal(cur->left)而忘了在返回后恢复状态，就会得到错误结果。257题的path.pop_back()是这四道题里最直观的回溯示范，搞懂了这道题，后面刷回溯算法专题会轻松很多。

第三点体会是：边界条件和空指针检查，永远值得多写一遍。110题要提前检查子树返回值是否为-1，404题要同时判断三个节点，222题要处理root为空。这些都不是“炫技”而是扎实的工程习惯。我前几次提交出错，十有八九是空指针判断漏了一个条件。

如果你也在刷这组题目，我建议按110、257、404、222的顺序来。这个顺序刚好对应了“最基础的递归求高度，到需要回溯的路径搜索，到父节点判断思想，再到利用结构性质的优化”，难度和思维跨度是平滑上升的。每道题都值得至少写两遍，第一遍看题解写，第二遍关掉题解自己默写。4道题都默写通过之后，你会发现二叉树相关的递归不仅不绕了，还能开始主动去设计递归函数的参数和返回值了。