企业官网建设流程全解析

最近几天不是在刷“代码随想录训练营”嘛，今天正好第13天，题目是四道二叉树：110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和、222.完全二叉树的节点个数。这四道题放在一起刷，卡哥的安排其实很有深意：前面两道练的是“递归返回值的运用”，后面两道练的是“条件判断与回溯过程中的细节”。四道题都不算难，但每一道都藏着一个特别容易让新手翻车的点。

如果你正在刷题，或者刚把二叉树的前中后序遍历弄明白，这篇总结应该能帮你少走不少弯路。我会把四道题的解题思路、完整代码、踩坑点全部摊开讲，按训练营的顺序来，内容比较长，建议收藏后边看边写。

1. 刷题前的整体思路：递归三部曲与单层拆解

1.1 为什么要先明确“递归函数要干什么”

二叉树这个结构天然就是递归的：一个节点的左子树、右子树，本质上还是一棵二叉树。所以只要涉及到二叉树，绝大多数题都是在写递归。但很多人在写递归的时候卡住，不是因为不会写“递归调用”，而是没想清楚三件事：

1. 函数参数是什么：哪些信息需要在递归过程中传递？
2. 函数返回值是什么：你期望从子问题里拿回什么信息？
3. 终止条件是什么：什么时候可以直接返回，不再递归？

代码随想录里反复说的“递归三部曲”，其实就是把这三个问题逐一定下来。我做二叉树题目时有个习惯：先在草稿纸上把这三行写出来，再写代码。看似很耽误时间，实际能省下大量调试时间。尤其今天这四道题，每道题对三要素的设定都不太一样，尤其是“返回值”，稍微想岔了，整段代码就会绕进死胡同。

1.2 深度和高度：被无数人混淆的两个概念

这四道题里，至少有“平衡二叉树”和“完全二叉树的节点个数”两道题，会直接牵扯到“深度”和“高度”的区别。这俩概念搞错，代码就会越写越乱。

• 深度（depth）：从根节点出发到某个节点所经过的边的条数。根节点的深度是0，越往下越深。
• 高度（height）：从某个节点出发到最远叶子节点所经过的边的条数。叶子的高度是0，越往上越高。

关键在于遍历方式：

• 求深度常见于前序遍历，因为你得先知道父节点的深度，才能算出子节点的深度，参数跟着传下去。
• 求高度常见于后序遍历，因为你要先知道左右子树的高度，才能算出当前节点的高度，靠返回值一层层传上来。

我用一个生活化的类比：深度是“你从山顶往下走了多少步”，高度是“你站在当前这个地方，往下看还有多少级台阶才到地面”。

今天这四道题，主战场其实是“高度”，也就是后序遍历。理解了这个点，后面写代码会顺很多。

2. 110. 平衡二叉树：用后序遍历的返回值做“体检”

2.1 题目解析与判断标准

平衡二叉树的定义很明确：每个节点的左右子树高度差的绝对值不超过1。注意是“每个节点”，不是只看根节点。这意味着你不能只在根节点算一次高度差就完事，必须保证整棵树所有子树都满足条件。

这道题如果从“高度”的角度切入，思路就非常自然：写一个函数，返回以当前节点为根节点的子树的高度。在这个函数里，我先递归拿左子树高度，再递归拿右子树高度，然后检查高度差。一旦发现超过了1，说明这棵子树已经不是平衡二叉树了，直接向上抛一个“异常”信息。

问题在于：递归函数的返回值是“高度”这种非负数，怎么表达“我此时已经不平衡了”？常用的技巧是用一个不可能出现的特殊值来标记，比如-1。遇到-1，上层递归立刻知道：子树有问题，整棵树不用再看了。

2.2 参考代码：一版O(n)的写法

下面是Java版本，也是我在训练营里最终采用的写法：

class Solution { public boolean isBalanced(TreeNode root) { return getHeight(root) != -1; } private int getHeight(TreeNode node) { if (node == null) { return 0; } int leftHeight = getHeight(node.left); // 左子树已经不平衡，直接向上返回-1，不再继续递归 if (leftHeight == -1) { return -1; } int rightHeight = getHeight(node.right); if (rightHeight == -1) { return -1; } // 高度差超过1，说明当前节点作为根节点，这棵树不平衡 if (Math.abs(leftHeight - rightHeight) > 1) { return -1; } // 当前子树高度 = 左右子树较高者 + 1（当前节点这一层） return Math.max(leftHeight, rightHeight) + 1; } }

几个关键点：

4. 空节点返回0：这是进入循环的基石，null节点高度为0，符合常理。
5. 先判-1再继续：一旦左右子树有一边已经不平衡了，整个函数的后续判断就没有意义，直接返回-1即可。这种“一旦发现故障就立刻报废”的写法，能让整棵树在一次遍历里完成校验，时间复杂度只有O(n)。
6. 返回的高度是“子树高度”：节点的高度等于左右子树高度的最大值加1。这一步很多人会写成左加右，那就完全错了，加的是“当前节点本身”这1层高度，不是把左右子树算在一起。

2.3 千万不要写“双重递归”

这道题最容易踩的坑，其实是下面这种写法：

public boolean isBalanced(TreeNode root) { if (root == null) return true; // 当前节点高度差是否超过1？ if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) { return false; } // 左右子树是否各自平衡？ return isBalanced(root.left) && isBalanced(root.right); } private int getHeight(TreeNode node) { if (node == null) return 0; return Math.max(getHeight(node.left), getHeight(node.right)) + 1; }

这段代码从逻辑上完全正确，但性能差很多。因为isBalanced每次遍历一个节点，都要调用一次getHeight，而getHeight会把以该节点为根的子树完整遍历一遍。也就是说，每个节点都被重复计算了高度，整棵树退化成O(n^2)的时间复杂度。

我从第一次接触这道题到现在，见过太多初学者写这种版本，因为“先算高度再判断”的想法太符合直觉了。面试的时候，如果遇到让你优化这道题，面试官其实想看的就是能不能把“算高度”和“判断平衡”合并在同一次递归里完成，也就是上面那版遇到-1就返回的写法。

3. 257. 二叉树的所有路径：回溯的入门必修题

3.1 路径收集的本质

“二叉树的所有路径”这道题，要求输出从根节点到每个叶子节点的完整路径，比如1->2->5。这本质上是一次深度优先遍历，只是遍历过程中需要“记住”走过来时经过的节点。

有个问题：二叉树的分支是有限的，遍历完一条路径后，你要原路退回去，再走另一条分支。退回的时候，这条路径上记录过的节点也必须同步删掉，不然路径会越来越长，全串在一起。这个“删掉已记录节点”的动作，就是回溯。

我用一个例子说明：假设从根节点1出发，先走左孩子2，2是叶子，记录1->2；接下来你要走右孩子4，如果不把2从路径里拿掉，新路径会变成1->2->4，这明显是错的，因为4是根节点的右孩子，它的路径应该是1->4。所以，从2返回根节点之前，必须把2踢出路径。

回溯就像是你在森林里做记号的绳子，走进一条死胡同，退出来时顺手把钉子拔掉，这样走到另一个路口时，手里的绳子才不会一团乱。

3.2 参考代码与回溯解释

这道题用前序遍历，因为路径的顺序是“根 → 叶”。参考代码如下：

class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); traversal(root, path, result); return result; } private void traversal(TreeNode node, List<Integer> path, List<String> result) { // 这行代码在进入每个节点时执行，把当前节点加入路径 path.add(node.val); // 叶子节点，收集结果 if (node.left == null && node.right == null) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < path.size() - 1; i++) { sb.append(path.get(i)).append("->"); } sb.append(path.get(path.size() - 1)); result.add(sb.toString()); return; } if (node.left != null) { traversal(node.left, path, result); path.remove(path.size() - 1); // 回溯：删除进入左孩子时加入的节点 } if (node.right != null) { traversal(node.right, path, result); path.remove(path.size() - 1); // 回溯：删除进入右孩子时加入的节点 } } }

这段代码里的回溯位置让很多新手困惑，我详细解释一遍回溯的逻辑链条：

• 调用traversal(1)时，先把1放入path。
• 发现1有左孩子2，于是调用traversal(2)，进入2时把2放入path，此时path为[1, 2]。
• 如果2是叶子，收集结果后直接return。注意，return时没有删除2，path还是[1, 2]。
• 回到traversal(1)中调用traversal(2)的位置，紧接着执行path.remove(path.size() - 1)，这一步删掉的就是2，path恢复为[1]。
• 然后再去递归右孩子4，进入4时把4放入path，此时path为[1, 4]，路径又变正确了。

也就是说，叶子节点的删除动作不是在自己这一层做的，而是由它的父节点在递归返回之后执行。这一点想明白，回溯就算入了门。

3.3 Java中的String与StringBuilder选择

在收集路径的时候，我用了StringBuilder来拼接，原因很简单：如果每次拼接都用String的+，Java会产生大量临时字符串对象。虽然这道题的数据量不大，不至于成为性能瓶颈，但写代码的人应该养成好习惯。

还有一个很隐蔽的Bug风险：如果不小心把StringBuilder对象直接放进结果集合，后续对它的修改会污染已经添加进结果里的路径。正确做法是先把StringBuilder转成String再放入result。上面代码里，我每次收集都是新建了一个StringBuilder，所以不存在这个问题。

另外，这道题也可以用字符串常量作为递归参数来写，这样连显式回溯都可以省掉：

private void traversal(TreeNode node, String path, List<String> result) { if (node == null) return; path = path + node.val; if (node.left == null && node.right == null) { result.add(path); return; } traversal(node.left, path + "->", result); traversal(node.right, path + "->", result); }

这段代码能跑通，但代价是每一层递归都会创建新的字符串对象。刷题阶段我不建议用这种写法，因为你会失去练习“回溯”的机会。回溯是DFS类题目的核心基本功，今天不练，后面遇到排列组合、岛屿问题还是会吃亏。

4. 404. 左叶子之和：判断条件藏在父节点那一层

4.1 左叶子的准确定义

“左叶子之和”这道题要求把所有左叶子的值加起来。什么叫左叶子？同时满足两个条件：

1. 它是某个节点的左孩子；
2. 它自己是叶子节点，也就是左右孩子都为空。

这看起来简单，但写代码的时候很容易犯一个错误：在递归遍历时判断“当前节点是不是叶子”，如果是叶子就加入结果。这种写法会把“右叶子”也加进去，比如下面这棵树的右叶子4，就不是左叶子。

1 / \ 2 4 / \ 5 6

正确的理解是：判断某节点是否为“左叶子”，必须在它的父节点那一层来判断，不能在节点自己那一层判断。因为到了节点自己这一层，你已经不知道它是左孩子还是右孩子了。

打个比方：你想知道“这辆车是不是停在车位里的第一辆”，你得站在车位入口看，而不是坐进车里看。坐进车里，你看到的世界永远是“前面有挡风玻璃，后面有座椅”，分不清车头朝里还是朝外。

4.2 参考代码与单层逻辑

我采用后序遍历写了一个简洁版本：

class Solution { public int sumOfLeftLeaves(TreeNode root) { return sumLeft(root); } private int sumLeft(TreeNode node) { if (node == null) { return 0; } int sum = 0; // 判断左孩子是否为左叶子，注意此时站在“父节点”这一层 if (node.left != null && node.left.left == null && node.left.right == null) { sum += node.left.val; } // 继续递归，把左右子树里的左叶子之和拼上来 sum += sumLeft(node.left); sum += sumLeft(node.right); return sum; } }

这段代码有三个值得留意的细节：

• 在进入node.left递归前，先看node.left本身是不是左叶子。如果是，直接累加，然后再去递归左子树。有人会问：既然node.left已经是叶子了，递归进去也只是返回0，为什么不跳过？其实不跳也没关系，因为递归进去，node.left为null或者无子节点，最终都会返回0。
• 我之所以专门写sum += sumLeft(node.left)，是因为左子树里还可能存在更深层的左叶子，比如左子树里某个节点的左孩子。所以不能因为node.left不是左叶子，就索性不去递归左子树了。
• 用后序遍历和用前序遍历在这道题里都行，因为累加操作的位置对最终结果没有影响。关键还是那个“在父节点判断左叶子”的思想。

4.3 新手最常犯的错误

我把这道题最常见的两种错误写法列出来，看看你有没有中招。

错误写法一：只判断叶子，不判断方向

if (node.left == null && node.right == null) { sum += node.val; }

这种写法会把所有叶子都算进来，结果天然偏大。

错误写法二：只判断“是左孩子”，不判断“是叶子”

if (node.left != null) { sum += node.left.val; }

这种写法会把所有左孩子都算进来，哪怕它并不是叶子，比如上面示例里的节点5。

大家看，这两个条件就像两个筛子，必须叠加在一起，才能精确捞到“左叶子”。我自己刷题时，就在这道题上栽过一次，把左子树i的根节点当成了左叶子。后来专门画了一棵三层树：根节点1、左孩子2、右孩子3，然后又在2下面挂了一个左孩子4，这才真正理解了“父节点视角”的含义。

5. 222. 完全二叉树的节点个数：想清楚“满二叉树”再下手

5.1 普通解法：递归数节点

这一题最简单、最不用动脑子的写法，就是普通二叉树递归遍历：

class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } return countNodes(root.left) + countNodes(root.right) + 1; } }

每个节点都会被访问一次，时间复杂度O(n)。在面试中，如果你能先写出这版，已经是合格的了。但题目里的“完全二叉树”四个字不是摆设，它意味着有更高效的解法。

完全二叉树和普通二叉树最大的区别在于：它的最后一层节点只可能从左到右连续出现，不会出现“右边有、左边没有”的断档情况。利用这个性质，可以做到比O(n)更快的节点计数。

5.2 利用完全二叉树性质的优化解法

优化的核心思想是：遇到一棵满二叉树，直接套公式计算节点数，不用傻傻地递归到底。满二叉树的节点数 = 2^h - 1，其中h是树的层高。

问题来了：怎么快速判断一棵子树是不是满二叉树？在完全二叉树里有个取巧的办法：

比较当前节点左子树一路向左的深度 和 右子树一路向右的深度。 如果两者相等，说明这棵子树是满二叉树。

为什么？因为完全二叉树的最后一层是连续排布的。如果不连续，左子树那一路往左的深度会比右子树一路往右的深度更深。反过来，如果左右深度相等，说明节点已经铺满到最后一层了，整棵树是满的。

我画一个简单例子：

1 / \ 2 3 / \ \ 4 5 7

这棵树不是满二叉树，因为节点3缺少左孩子。从根节点1出发，左子树一路向左是1->2->4，深度为2；右子树一路向右是1->3->7，深度也是2，但是等一下，节点3的右孩子是7，如果节点3没有左孩子，那么从“一路向右”的深度和“一路向左”的深度，都是2，我们却会误判它满。

不对，这里需要再细想：按照代码，while(right != null) { right = right.right; rightDepth++; }，right从root.right=3开始，3不为null，depth=1，right=3.right=7，7不为null，depth=2，right=null，结束。所以rightDepth=2；left从root.left=2开始，2不为null，depth=1，left=2.left=4，4不为null，depth=2，left=null，结束。所以leftDepth=2。两者相等，我们就会错误地返回7（2^3-1）。但这棵树实际节点数是6。问题出在哪里？

啊，我意识到这个判断条件其实是：判断以当前节点为根的子树，是否“最左深度”等于“最右深度”。在上面的例子里，root的左子树深度（只沿最左路径）是2，右子树的深度（只沿最右路径）是2，但这棵树并不是满的。

那我们还能用这个条件吗？实际上，这个条件是充分条件：如果最左深度等于最右深度，那么这棵完全二叉树一定是满的。让我重新验证一下：节点3有右孩子7但没有左孩子，这时右最右深度怎么可能是2？root.right=3，一路向右是3->7，是的，可以到达深度2。root.left=2，一路向左是2->4，到达深度2。所以两者相等，但树不满。

所以这个条件是不正确的？不对，让我再确认完全二叉树的定义。完全二叉树最后一层节点从左到右连续。上面的树，最后一层有4、5、7三个节点，它们确实是从左到右连续的吗？3没有左孩子，所以7实际上悬空了，这棵树根本就不是完全二叉树。根据题目定义，输入的树是保证是完全二叉树的。所以，在完全二叉树的前提下，如果最左深度等于最右深度，那么这棵子树一定是满二叉树。因为完全二叉树不允许“右深左浅”这种空心结构。但我的例子不是完全二叉树，所以不在题目考虑范围内。

也就是说，这个判断只在“给定的二叉树是完全二叉树”这个大前提下才成立。题目保证了这个前提，所以可以用。我在博文里会补充这个前提的提醒。

参考代码：

class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } // 判断以root为根的子树是不是满二叉树 TreeNode left = root.left; TreeNode right = root.right; int leftDepth = 0; int rightDepth = 0; while (left != null) { left = left.left; leftDepth++; } while (right != null) { right = right.right; rightDepth++; } // 相等说明是满二叉树，直接套公式 if (leftDepth == rightDepth) { return (2 << leftDepth) - 1; // 等于 2^(leftDepth+1) - 1 } // 不是满二叉树，老老实实递归数 return countNodes(root.left) + countNodes(root.right) + 1; } }

这段代码里，(2 << leftDepth) - 1到底是什么？以根节点只有一个节点的情况为例：leftDepth=0，2 << 0 = 2，2 - 1 = 1，节点数是1，正确。根节点有3个节点时，leftDepth=1，2 << 1 = 4，4 - 1 = 3，正确。其实这行等价于Math.pow(2, leftDepth + 1) - 1，但因为运算符优先级和效率原因，用移位写更简洁，也更符合编程面试的调性。

5.3 为什么时间复杂度是O(log^2 n)

这个优化解法值得关注的地方在于：它不是把整棵树完整遍历一遍，而是“剪”掉了很多满二叉子树。每次递归到一个节点，先花O(log n)的时间沿左右边界走到底，判断子树是不是满的；如果是，直接返回，不再深入。如果一棵完全二叉树在每一层都触发了“半满”的情况，递归深度是O(log n)，每一层判断又花O(log n)，总时间复杂度是O(log n * log n)，也就是O(log^2 n)。

可能有人会觉得，这个优化对很小的数据没意义。但面试官看重的是你知不知道“完全二叉树”这个性质，以及能不能写出这种针对性优化。这属于“扎实掌握基础”和“只会做模板题”的分水岭。

6. 第13天的避坑心得与两个小技巧

6.1 递归函数到底要不要返回值？

四道题刷完，我最大的收获之一，就是对“递归函数返回值”这件事有了更深的体会。以前写递归，总想着“我要返回什么结果”，今天四道题给了四个不同的答案：

一句话总结：如果你需要子问题的结果来拼装父问题的结果，就一定要有返回值；如果你只是遍历整棵树，边走边往外面收集东西，返回值就可以空着。这个判断标准非常基础，但很多刷题卡壳的人，都是卡在这一步没想清楚。

6.2 回溯与递归调用的配对关系

“二叉树的所有路径”这道题，让我把回溯的机制彻底理清了。核心就一句话：递归调用进入子节点时，路径是什么状态，递归返回后就要恢复成什么状态。最好的验证方式是“对称检查”：你在递归之前往path里加了节点，递归返回后就要在对应的位置删除它。

我还发现，用List<Integer>做路径时，如果路径里有多个节点，删除时要小心下标别越界。最常见的越界场景是：递归内已经return了，返回到父节点后，父节点傻乎乎地又删了一次。记住，return不会触发父节点的删除动作，父节点的删除动作是在递归调用语句之后才执行的，两者并不会冲突，但你在心里要对“谁删自己，谁删孩子”有清晰的账本。

6.3 手写打印二叉树，调试速度直接翻倍

刷二叉树题目，最怕的就是代码输出结果不对，但脑内调试又看不出问题。我今天的做法是：写一个简单的printTree方法，用前序遍历方式把树打出来，同时带上左右孩子的信息，快速定位递归过程在哪里开始出错。

public void printTree(TreeNode node, String prefix) { if (node == null) { System.out.println(prefix + "null"); return; } System.out.println(prefix + node.val); printTree(node.left, prefix + "L:"); printTree(node.right, prefix + "R:"); }

调试257题的时候，我一路打印出“进入第几个节点、当前path是什么、是否是叶子”，很快就看到了path在回溯前后是否恢复正确。这种小工具不值得写得太复杂，能看清节点访问顺序和路径状态就够了。

6.4 今日刷题顺序的小建议

如果你是跟着训练营进度走的，我强烈建议按“110 → 257 → 404 → 222”的顺序做，不要乱跳。理由很简单：

• 110题先练“递归返回值”，而且必须把高度计算和平衡判断揉在一起，这会逼你想清楚后序遍历的返回值。
• 257题换个玩法，返回值变成void，改用参数收集结果，并且引入回溯，只是一个新维度。
• 404题在递归思路上是110的简化版，但多了“在父节点层判断条件”这个细节。
• 222题则是把“递归数数”和“利用数据结构特性优化”放到一起，收尾很完美。

我自己有个体会：单独刷一道题，往往只是在背模板；但把一个专题里的几道题连起来刷，才能真正理解为什么这题用前序、那题用后序，为什么这个函数要返回值、那个函数不需要。这就是代码随想录训练营“按专题刷题”的价值所在。

今天是第13天，四道题做完，我把笔记整理成这篇文章。说实话，写到222题的时候，我还专门用一个小树手动推演了一遍(2 << leftDepth) - 1这个公式，因为平时用Math.pow习惯了，突然切换到移位运算反而有点不踏实。这也是我刷题的一个小方法：复杂的地方，别急着敲代码，先拿张纸画一画，在纸上把每一步的值标出来，再回来写代码，基本一遍就过。

最后再分享一个细节：这四道题的代码量都不大，但每一道都值得你尝试“不看题解，下午重新写一遍”。隔几个小时或者第二天再做一次，你会发现记忆不是靠看出来的，而是靠“在空白的编辑器里，从零到一敲出来”练出来的。我是打算明天把257题用两种写法（带回溯的List和字符串常量版）各写一遍，你要是也刷到这一天，不妨一起试试。