最近几天不是在刷“代码随想录训练营”嘛今天正好第13天题目是四道二叉树110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和、222.完全二叉树的节点个数。这四道题放在一起刷卡哥的安排其实很有深意前面两道练的是“递归返回值的运用”后面两道练的是“条件判断与回溯过程中的细节”。四道题都不算难但每一道都藏着一个特别容易让新手翻车的点。如果你正在刷题或者刚把二叉树的前中后序遍历弄明白这篇总结应该能帮你少走不少弯路。我会把四道题的解题思路、完整代码、踩坑点全部摊开讲按训练营的顺序来内容比较长建议收藏后边看边写。1. 刷题前的整体思路递归三部曲与单层拆解1.1 为什么要先明确“递归函数要干什么”二叉树这个结构天然就是递归的一个节点的左子树、右子树本质上还是一棵二叉树。所以只要涉及到二叉树绝大多数题都是在写递归。但很多人在写递归的时候卡住不是因为不会写“递归调用”而是没想清楚三件事函数参数是什么哪些信息需要在递归过程中传递函数返回值是什么你期望从子问题里拿回什么信息终止条件是什么什么时候可以直接返回不再递归代码随想录里反复说的“递归三部曲”其实就是把这三个问题逐一定下来。我做二叉树题目时有个习惯先在草稿纸上把这三行写出来再写代码。看似很耽误时间实际能省下大量调试时间。尤其今天这四道题每道题对三要素的设定都不太一样尤其是“返回值”稍微想岔了整段代码就会绕进死胡同。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; } }几个关键点空节点返回0这是进入循环的基石null节点高度为0符合常理。先判-1再继续一旦左右子树有一边已经不平衡了整个函数的后续判断就没有意义直接返回-1即可。这种“一旦发现故障就立刻报废”的写法能让整棵树在一次遍历里完成校验时间复杂度只有O(n)。返回的高度是“子树高度”节点的高度等于左右子树高度的最大值加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出发先走左孩子22是叶子记录1-2接下来你要走右孩子4如果不把2从路径里拿掉新路径会变成1-2-4这明显是错的因为4是根节点的右孩子它的路径应该是1-4。所以从2返回根节点之前必须把2踢出路径。回溯就像是你在森林里做记号的绳子走进一条死胡同退出来时顺手把钉子拔掉这样走到另一个路口时手里的绳子才不会一团乱。3.2 参考代码与回溯解释这道题用前序遍历因为路径的顺序是“根 → 叶”。参考代码如下class Solution { public ListString binaryTreePaths(TreeNode root) { ListString result new ArrayList(); ListInteger path new ArrayList(); traversal(root, path, result); return result; } private void traversal(TreeNode node, ListInteger path, ListString 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时没有删除2path还是[1, 2]。回到traversal(1)中调用traversal(2)的位置紧接着执行path.remove(path.size() - 1)这一步删掉的就是2path恢复为[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, ListString 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 左叶子的准确定义“左叶子之和”这道题要求把所有左叶子的值加起来。什么叫左叶子同时满足两个条件它是某个节点的左孩子它自己是叶子节点也就是左右孩子都为空。这看起来简单但写代码的时候很容易犯一个错误在递归遍历时判断“当前节点是不是叶子”如果是叶子就加入结果。这种写法会把“右叶子”也加进去比如下面这棵树的右叶子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.right3开始3不为nulldepth1right3.right77不为nulldepth2rightnull结束。所以rightDepth2left从root.left2开始2不为nulldepth1left2.left44不为nulldepth2leftnull结束。所以leftDepth2。两者相等我们就会错误地返回72^3-1。但这棵树实际节点数是6。问题出在哪里啊我意识到这个判断条件其实是判断以当前节点为根的子树是否“最左深度”等于“最右深度”。在上面的例子里root的左子树深度只沿最左路径是2右子树的深度只沿最右路径是2但这棵树并不是满的。那我们还能用这个条件吗实际上这个条件是充分条件如果最左深度等于最右深度那么这棵完全二叉树一定是满的。让我重新验证一下节点3有右孩子7但没有左孩子这时右最右深度怎么可能是2root.right3一路向右是3-7是的可以到达深度2。root.left2一路向左是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^(leftDepth1) - 1 } // 不是满二叉树老老实实递归数 return countNodes(root.left) countNodes(root.right) 1; } }这段代码里(2 leftDepth) - 1到底是什么以根节点只有一个节点的情况为例leftDepth02 0 22 - 1 1节点数是1正确。根节点有3个节点时leftDepth12 1 44 - 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 递归函数到底要不要返回值四道题刷完我最大的收获之一就是对“递归函数返回值”这件事有了更深的体会。以前写递归总想着“我要返回什么结果”今天四道题给了四个不同的答案题目递归函数需要返回的信息是否必须用返回值110. 平衡二叉树子树高度或-1标记不平衡必须否则无法判断高度差257. 二叉树的所有路径不需要返回信息用参数收集结果否void即可404. 左叶子之和子树下所有左叶子之和可用返回值也可累加全局变量222. 完全二叉树的节点个数子树节点个数必须一句话总结如果你需要子问题的结果来拼装父问题的结果就一定要有返回值如果你只是遍历整棵树边走边往外面收集东西返回值就可以空着。这个判断标准非常基础但很多刷题卡壳的人都是卡在这一步没想清楚。6.2 回溯与递归调用的配对关系“二叉树的所有路径”这道题让我把回溯的机制彻底理清了。核心就一句话递归调用进入子节点时路径是什么状态递归返回后就要恢复成什么状态。最好的验证方式是“对称检查”你在递归之前往path里加了节点递归返回后就要在对应的位置删除它。我还发现用ListInteger做路径时如果路径里有多个节点删除时要小心下标别越界。最常见的越界场景是递归内已经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和字符串常量版各写一遍你要是也刷到这一天不妨一起试试。