第十五天的题单一拉出来我第一反应是“这四道题都不难”。可真动手刷完才发现它们凑在一起是有讲究的110、257、404、222几乎把二叉树递归里最核心的几件事——后序求高度、前序收集路径、用父节点视角判断特殊节点、利用完全二叉树特性优化——各出了一道代表题。如果你也在跟代码随想录算法训练营刷二叉树这一天值得停下来多琢磨一会儿别急着追求AC数量把这四道题的“为什么”吃透后面写回溯和递归会顺手很多。1. 第十五天的四道题正好凑齐二叉树递归的三种套路1.1 一天的题单难度梯度其实很讲究先说结论这四道题按难度排大概是 404 257 ≈ 110 222。但难度并非唯一线索更重要的是它们在递归思路上刚好互补。110平衡二叉树要求你从子树返回高度本质是后序遍历左-右-中因为必须先知道左右子树的高度才能判断当前节点是否平衡。257二叉树的所有路径要求从根走到叶子边收集边记录本质是前序遍历中-左-右因为路径的顺序天然是从根开始的。404左叶子之和看起来简单但真正的坎在于“左叶子”这个定义本身——它必须靠父节点来判定这是很多新手绕不过去的弯。222完全二叉树的节点个数如果只求暴力解一两分钟就能写出来可一旦想到“完全二叉树”四个字你就应该停下来想一想能不能利用满二叉树的数学性质把复杂度从 O(n) 降到 O(log^2 n)。所以这一天的题单相当于把二叉树递归里的三种“手感”都练了一遍求值用后序、收集路径用前序、特性利用靠观察和数学推导。这四道题我强烈建议不要只看题解自己先写一版再对照优化版收获会翻倍。1.2 适合谁来读读之前需要什么基础这篇复盘适合正在刷二叉树、但还处在“每次递归都要重新想一遍”阶段的读者。如果你能区分先序/中序/后序的区别、能写出递归版前序遍历那么接下来的内容你完全吃得下。如果你连递归都还有些发怵也没关系我会先把每道题的递归三步曲拆开讲清楚。刷二叉树题目我一直坚持一个理念不要背题要背“套路”。树这类结构天生适合递归因为树的子树还是树。而递归的难点从来不在“怎么写”而在“这个函数该返回什么、什么时候停下来、单层逻辑做什么”。这四道题恰好就是把这三个问题分别放大给你看。2. 110. 平衡二叉树先分清高度和深度后序递归才不会乱2.1 题目在考什么一颗树到底怎么算“平衡”力扣 110 的平衡二叉树定义每个节点的左右子树高度差绝对值不超过 1。网上很多题解写得很随意但这里有个概念陷阱就是“高度”和“深度”经常被混着用。我自己的记忆方法是深度是往下的从根到你所在节点高度是往上的从你所在节点到叶子。所以根节点的深度最大叶子节点的深度最小反过来叶子节点的高度最小约定为 1根节点的高度是整棵树的最大深度。判断一颗树是否平衡逻辑上需要先知道左右子树各自有多高再比较差值。这意味着在递归返回时你必须要得到“这棵子树到底有多高”这个数字。如果某个子树已经不平衡了还需要继续算它的高度吗不需要直接向上传递一个“失败信号”让整棵树提前结束。这个题目最容易犯的错误是想着“在每个节点用前序遍历求它的深度再比较左右孩子深度的差”。这个思路看着对但实际上你求出来的“深度”并不是该节点子树的高度而且每到一个节点都重新向下数一遍深度会带来大量重复计算。正确姿势只有一个用后序遍历求高度。2.2 递归三部曲落地用-1既当高度又当失衡标记递归不管多绕先想三件事参数和返回值是什么、终止条件是什么、单层逻辑做什么。这道题我要返回高度但还要额外表达“这颗子树已经不平衡了”。两个信息合并我的返回值就用一个 int正常情况返回高度一旦发现不平衡就返回 -1。这样上层节点拿到 -1 后立刻就能判断出整棵树已经不平衡没必要再往下朝右子树递归了。class Solution { public boolean isBalanced(TreeNode root) { return getHeight(root) ! -1; } private int getHeight(TreeNode node) { if (node null) { return 0; // 空节点高度为0 } int leftHeight getHeight(node.left); if (leftHeight -1) { return -1; // 左子树已经不平衡 } int rightHeight getHeight(node.right); if (rightHeight -1) { return -1; // 右子树已经不平衡 } // 当前节点的平衡性左右高度差不能超过1 if (Math.abs(leftHeight - rightHeight) 1) { return -1; } // 返回当前节点作为根的子树的真实高度 return Math.max(leftHeight, rightHeight) 1; } }这段代码建议亲手抄一遍再默写一遍。注意最后一行是Math.max(left, right) 1不是Math.min。这个 1 代表把当前节点自己也算进高度里这是整段递归字数最少却最容易出错的地方。2.3 提前返回的剪枝效果别把明明不平衡的子树继续算下去递归版里连续两个if (leftHeight -1) return -1;看起来多此一举实际是剪枝的精髓。我刷题时一开始偷懒省略了这两个判断心想反正最后Math.abs也会发现不平衡。但仔细一想如果左子树已经返回 -1说明左子树内部已经失衡这时候继续算右子树的高度没有任何意义纯属浪费时间。极端一点的情况是这样一颗树根节点的左子树严重失衡而右子树是节点数量极大的完全二叉树。如果不剪枝左子树发现失衡后代码还要去把右子树完整遍历一遍白白花费 O(n) 时间剪枝后左子树返回 -1 的那一刹那整个递归就一路向上退出右子树根本不会被访问到。这种“短路求值”思想在后面的回溯剪枝、动态规划优化里会反复出现越早习惯越省力。2.4 迭代思路能懂更好不懂也不影响做题递归版已经足够应付面试和笔试但面试官偶尔会追问一句“你能用迭代写吗”。迭代思路其实是用显式栈模拟后序遍历同时用一个哈希表记录每个节点的高度。基本套路是两层第一层用栈模拟“左-右-中”的后序访问顺序。遍历到中间节点时先不断把左孩子、右孩子压栈确保左右子树都处理完了才轮到中间节点。第二层每个中间节点出栈时从哈希表里查询左右子树的高度比较差值然后把当前节点的高度Math.max(left, right) 1存进哈希表。我在这里不放完整迭代代码因为后序迭代本身比较绕很容易把初学者整懵。如果你目前还在建立递归直觉优先吃透递归版等递归版熟练了再看迭代作为思维扩展。面试中能写出简洁递归并解释清楚剪枝逻辑已经能拿不错的分数。3. 257. 二叉树的所有路径前序遍历收集路径递归返回时记得撤销3.1 为什么一定要前序遍历257 题要求返回所有从根到叶子的路径比如[1-2-5, 1-3]。路径的起点永远是根顺序永远是“根在左、叶子在右”所以遍历顺序天然就是先访问根再访问左孩子再访问右孩子也就是前序遍历。中序和后序遍历都会把根节点留在中间或最后处理你想按“从根到叶子”的顺序拼接路径还得额外处理字符串顺序非常别扭。这也是一个判断经验看到“从根到叶子”这种强依赖顺序的需求优先想前序遍历。3.2 两种实现String的天然回溯 与 StringBuilder的显式回溯这道题最直观的写法是递归时传一个 String因为 Java 的 String 是不可变的每次拼接都会生成新对象天然帮你“隔离”了路径污染。class Solution { public ListString binaryTreePaths(TreeNode root) { ListString result new ArrayList(); if (root null) { return result; } dfs(root, , result); return result; } private void dfs(TreeNode node, String path, ListString result) { // 到达叶子生成一条完整路径 if (node.left null node.right null) { result.add(path node.val); return; } String nextPath path node.val -; if (node.left ! null) { dfs(node.left, nextPath, result); } if (node.right ! null) { dfs(node.right, nextPath, result); } } }这种写法的优点是思路清晰新手也好懂缺点是每层递归都会新建字符串在节点数量很大的场景下会有一定开销。但算法训练阶段先跑通逻辑比抠性能重要。用可变对象就得小心了。拿 StringBuilder 举例由于它是可变的递归返回后如果不手动“撤销”刚才追加的内容左子树残留的路径片段会污染右子树的拼接结果。private void dfs(TreeNode node, StringBuilder sb, ListString result) { // 记录进入当前节点前 sb 的长度方便退出时回退 int len sb.length(); if (len 0) { sb.append(-); } sb.append(node.val); if (node.left null node.right null) { result.add(sb.toString()); } else { if (node.left ! null) { dfs(node.left, sb, result); } if (node.right ! null) { dfs(node.right, sb, result); } } // 核心回溯恢复到进入当前节点之前的状态 sb.setLength(len); }重点看最后一行sb.setLength(len)。我在很多培训班同学的代码里见过这种 bug字符串拼接对了结果忘了回退最后输出的路径越长越长或者把左子树的节点串到了右子树路径里。如果你也遇到路径“串味”的情况十有八九是撤销没写对。3.3 边界条件空树、单节点和“1-”的干扰这道题的边界条件不多但每一个都很容易踩空树返回空列表。我在代码开头就先判了root null。只有一个根节点路径应该是1而不是1-。这个“多余的 -”是新手高频翻车点。所以拼接逻辑里我判断了len 0才加箭头保证根节点前没有-。叶子节点的判断必须严格为node.left null node.right null。只判断一边为空是不严谨的比如一个节点只有左孩子没有右孩子它不是叶子路径还必须继续走到真正的叶子。我的建议是写完代码后自己输入三个测试用例[]、[1]、[1,2,3]手算一下期望输出再跑基本能把边界问题全部暴露出来。3.4 这会是你第一次真正理解“回溯”结构回溯这个词在 257 这道题里被体现得淋漓尽致。你在 StringBuilder 里追加节点进入子树然后再递归回来把字符串缩短——这就是标准回溯模板的原型。把这段逻辑抽象一下记录当前现场 做出选择追加当前节点 递归进入下一层 撤销选择回到现场这个模板你会反复见到组合问题、排列问题、子集问题本质上都是这种“做选择-递归-撤销”的循环。所以 257 看起来只是二叉树路径题实际上是你第一次在代码里直观地看见回溯。我强烈建议你在刷完这道题后把上面的抽象模板抄在笔记里后面学回溯时会感谢今天的自己。4. 404. 左叶子之和左叶子的定义比想象中更容易绕晕4.1 “左叶子”的完整定义与两个反直觉例子“左叶子之和”听起来很简单把左叶子节点上的值加起来。但什么是左叶子必须先给它一个严谨定义这个节点是某个节点的左孩子这个节点自己没有左右孩子。有两点反直觉的地方要注意。第一一个节点即使是右子树的节点只要它是父节点的左孩子同时是叶子就算左叶子。第二根节点哪怕没有左右孩子也不算左叶子因为它没有父节点没有“左孩子”这个身份。举个容易想歪的例子7 / \ 5 6 / 8这里 8 是 6 的左孩子同时 8 自己也是叶子所以 8 是左叶子它的值应该被计入。很多人看到“左叶子”三个字下意识以为只有整棵树的左半边才算这就错了。“左”这个属性只和父节点相关和它在整棵树里的位置无关。再来一个更刁钻的1 / \ 2 3 / \ 4 54 是 2 的左孩子、是叶子计入5 是 2 的右孩子即使它是叶子也不计数。所以这一棵树的左叶子之和是 4。4.2 递归写法用父节点视角去判定孩子既然左叶子的判定依赖于“父节点”递归遍历时就别指望在访问到某个节点的时候只靠它自己判断而应该在访问父节点时检查它的左孩子。class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } int sum 0; // 当前节点的左孩子是叶子如果是直接累加 if (root.left ! null root.left.left null root.left.right null) { sum root.left.val; } // 左子树里可能还有左叶子继续递归 sum sumOfLeftLeaves(root.left); // 右子树里也可能有左叶子比如4.1里的8不能漏掉 sum sumOfLeftLeaves(root.right); return sum; } }注意最后两行左子树要递归右子树也要递归。哪怕右孩子本身是叶子如果它下面是空的递归进去返回 0但如果右子树内部存在“父节点的左孩子是叶子”的情况这部分值必须被统计到。漏递归右子树是这道题最常见的逻辑错误。还有一种更极简的写法把所有判断都浓缩进一个递归返回public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } if (root.left ! null root.left.left null root.left.right null) { return root.left.val sumOfLeftLeaves(root.right); } return sumOfLeftLeaves(root.left) sumOfLeftLeaves(root.right); }这个版本把“左孩子是左叶子”和“递归找其他左叶子”合并成一行代码更短但可读性略差。我还是推荐第一种写法因为面试时你需要边写边讲逻辑拆开更利于沟通。4.3 迭代写法栈里弹出的每个节点都可以做一次检查递归本质上是系统帮你维护了一个调用栈迭代写法无非是把它变成显式栈。用前序、中序、后序哪种都行因为这道题只需要把所有节点拜访一遍顺序不影响累加结果。public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } DequeTreeNode stack new ArrayDeque(); stack.push(root); int sum 0; while (!stack.isEmpty()) { TreeNode node stack.pop(); // 每次弹出一个节点先检查它的左孩子 if (node.left ! null node.left.left null node.left.right null) { sum node.left.val; } if (node.left ! null) { stack.push(node.left); } if (node.right ! null) { stack.push(node.right); } } return sum; }这里有个小优化点左叶子节点本身不需要再压入栈因为判断它是不是左叶子在父节点出栈时就已经完成了。真正需要继续压栈的是那些“可能含有更多左叶子”的子树。所以你可以像我上面这样先不管三七二十一左右孩子都压栈简单清晰也可以对左叶子节点额外做剪枝不把它压栈减少一次无意义的弹出。两者都正确写你顺手的。4.4 边界情况对照表场景期望结果背后的原因空树0没有节点可加只有一个根节点0根节点没有父节点不是任何人的左孩子根节点只有右孩子右孩子是叶子0右叶子不计数根节点的左孩子是叶子加左孩子值左孩子同时满足“是父亲的左孩子”和“是叶子”右子树里存在父节点的左叶子需要计入“左”只取决于父节点的左侧关系写代码前先把这个表在心里过一遍基本可以写一次就 AC。5. 222. 完全二叉树的节点个数从O(n)到O(log^2 n)的特性红利5.1 最朴素的解法任何二叉树都能数先别管“完全二叉树”这几个字把题目当成“给我任意一颗二叉树统计节点数”。这几乎是递归最入门级的题目public int countNodes(TreeNode root) { if (root null) { return 0; } return 1 countNodes(root.left) countNodes(root.right); }这行逻辑不需要动脑子当前节点算一个加上左子树的节点数再加上右子树的节点数。用层序遍历BFS也能做维护一个队列每弹出一个节点计数加 1然后把左右孩子入队。两种解法都是 O(n) 的时间复杂度。面试时先回答这个版本是稳妥的它证明你有基础能力。但面试官如果追问“这棵树除了是二叉树还是完全二叉树你能利用这个条件吗”就到了今天题单的关键部分。5.2 满二叉树公式带来的优化思路完全二叉树有一个很强的性质除了最后一层其他层都是满的而且最后一层的节点都尽可能靠左排列。这意味着对完全二叉树里的任何一个子树它有可能是满二叉树也有可能不是。怎么快速判断某棵子树是不是满二叉树看两个深度从它的左孩子出发一路朝左下走能走几步从它的右孩子出发一路朝右下走能走几步。如果两边步数相等说明左子树和右子树的最外边界高度一样——它是一棵满二叉树。满二叉树的节点数有现成公式2^h - 1其中 h 是层数。一步不用递归直接套公式。如果两边步数不相等说明这棵子树没满那就只能用老办法节点数 1 左子树节点数 右子树节点数递归往下分解。由于完全二叉树的特殊结构递归每一层都会砍掉一半“不确定区域”总体效率远高于 O(n)。5.3 递归实现与容易写错的一行位运算优化版代码如下public int countNodes(TreeNode root) { if (root null) { return 0; } int leftDepth 0; int rightDepth 0; TreeNode left root.left; TreeNode right root.right; while (left ! null) { leftDepth; left left.left; } while (right ! null) { rightDepth; right right.right; } // 如果左外边界和右外边界深度相等说明这棵子树是满二叉树 if (leftDepth rightDepth) { // 满二叉树节点数 2^(leftDepth1) - 1 return (2 leftDepth) - 1; } // 不是满二叉树递归去左右子树里继续判断 return 1 countNodes(root.left) countNodes(root.right); }这行位运算是整个代码里最容易被写错的一行。我见过很多人写成(1 leftDepth) - 1算出来的结果总是少节点。原因在于我的leftDepth是“沿最左侧走的时候经过的边的数量”不是“层数”。比如只有根节点的树走 0 条边leftDepth 0但满二叉树节点数是 1也就是2^(01) - 1 1。用位运算表达就是(2 0) - 1 1。如果写成(1 0) - 1 0根节点都被你数丢了。如果你对位运算不熟用Math.pow(2, leftDepth 1) - 1效果完全一样只是稍慢。我不建议为了炫技而用位运算前提是你真明白2 x的含义。5.4 复杂度对比与二分思路的一句话说明普通递归复杂度 O(n)优化版复杂度 O(log^2 n)。怎么估算的每调用一次递归就会在两个 while 循环里沿边界往下走这一步是 O(log n)而递归的深度最多也是 O(log n)——因为完全二叉树的树高是对数级的。两个 O(log n) 相乘就是 O(log^2 n)。举一个直观的数字假设树里有 10 亿个节点普通递归要真的访问 10 亿个节点优化版大约只需要几千次操作。这个差距在极端测试数据下是肉眼可见的。力扣官方还有一种更进阶的解法先确定树的高度再二分最后一层的节点数量用位掩码验证某个编号对应的节点是否存在。思路很漂亮但训练营阶段能把“满二叉树直接套公式”这个优化想明白已经超过了大多数刷题者。我这里不展开先把基础优化吃透。6. 四道题刷完我总结的二叉树递归检查清单6.1 递归三部曲在这四道题上的映射如果要把今天四道题浓缩成一张思维地图那它们就是在反复回答三个问题。第一这个函数该返回什么。110 返回子树高度并用 -1 表达“不平衡”257 不需要返回具体值只需要把路径写进结果集404 返回左叶子之和222 返回节点个数。返回值定了递归的骨架就定了。第二什么时候停下来。树的递归几乎无一例外第一反应永远是“空节点怎么处理”。110 里空节点返回 0257 里空节点直接 return404 里空节点返回 0222 里空节点返回 0。然后再考虑真正的“终结条件”比如 257 的叶子节点要把路径收集进结果集。第三单层逻辑做什么。这个最灵活110 在单层比较高度差257 在单层拼接路径404 在单层判断左孩子是否为叶子222 在单层判断是否为满二叉树。单层逻辑写对了递归基本成功了一大半。6.2 一张表记住四道题的易错点题目核心遍历方式返回值/状态最高频易错点110 平衡二叉树后序遍历int 高度-1 表示失衡混淆高度深度忘了剪枝257 二叉树的所有路径前序遍历无返回值收集结果StringBuilder 忘记回溯多出“-”404 左叶子之和任意遍历整型累加和漏递归右子树根节点误判为左叶子222 完全二叉树节点个数后序 特性判断int 节点数满二叉树公式里的 1 写错位运算搞混这张表我建议抄在解题笔记里刷题中期拿出来复习一遍比再刷十道新题更有用。尤其是 257 的“回溯”和 222 的“满二叉树公式”是训练营同学互相提问时最容易翻车的地方。6.3 最后一件事把“为什么”讲清楚第十五天刷完我最大的体会是二叉树的递归题从来不靠背题而是靠把“遍历顺序、返回值、边界条件”这三个问题想清楚。四道题看起来各自独立其实是同一套思维在四个场景下的反复演练。所以如果今天你也刚好刷到这里别急着去做下一批题目。先把每道题的代码遮住口头给自己讲一遍“110 为什么用后序257 为什么用前序404 为什么可以随便用任何顺序222 的满二叉树公式为什么是 2 的 h 次方减 1”这几个问题能流利答出来今天的四道题才算真正消化了。后面遇到的二叉树递归题大概率都是这些套路的变形而已。 
长河君 · 2026/10/24 4:40:20 · 阅读 1.2k 二叉树递归四题精讲：平衡判断、路径回溯、左叶子与完全二叉树优化
第十五天的题单一拉出来我第一反应是“这四道题都不难”。可真动手刷完才发现它们凑在一起是有讲究的110、257、404、222几乎把二叉树递归里最核心的几件事——后序求高度、前序收集路径、用父节点视角判断特殊节点、利用完全二叉树特性优化——各出了一道代表题。如果你也在跟代码随想录算法训练营刷二叉树这一天值得停下来多琢磨一会儿别急着追求AC数量把这四道题的“为什么”吃透后面写回溯和递归会顺手很多。1. 第十五天的四道题正好凑齐二叉树递归的三种套路1.1 一天的题单难度梯度其实很讲究先说结论这四道题按难度排大概是 404 257 ≈ 110 222。但难度并非唯一线索更重要的是它们在递归思路上刚好互补。110平衡二叉树要求你从子树返回高度本质是后序遍历左-右-中因为必须先知道左右子树的高度才能判断当前节点是否平衡。257二叉树的所有路径要求从根走到叶子边收集边记录本质是前序遍历中-左-右因为路径的顺序天然是从根开始的。404左叶子之和看起来简单但真正的坎在于“左叶子”这个定义本身——它必须靠父节点来判定这是很多新手绕不过去的弯。222完全二叉树的节点个数如果只求暴力解一两分钟就能写出来可一旦想到“完全二叉树”四个字你就应该停下来想一想能不能利用满二叉树的数学性质把复杂度从 O(n) 降到 O(log^2 n)。所以这一天的题单相当于把二叉树递归里的三种“手感”都练了一遍求值用后序、收集路径用前序、特性利用靠观察和数学推导。这四道题我强烈建议不要只看题解自己先写一版再对照优化版收获会翻倍。1.2 适合谁来读读之前需要什么基础这篇复盘适合正在刷二叉树、但还处在“每次递归都要重新想一遍”阶段的读者。如果你能区分先序/中序/后序的区别、能写出递归版前序遍历那么接下来的内容你完全吃得下。如果你连递归都还有些发怵也没关系我会先把每道题的递归三步曲拆开讲清楚。刷二叉树题目我一直坚持一个理念不要背题要背“套路”。树这类结构天生适合递归因为树的子树还是树。而递归的难点从来不在“怎么写”而在“这个函数该返回什么、什么时候停下来、单层逻辑做什么”。这四道题恰好就是把这三个问题分别放大给你看。2. 110. 平衡二叉树先分清高度和深度后序递归才不会乱2.1 题目在考什么一颗树到底怎么算“平衡”力扣 110 的平衡二叉树定义每个节点的左右子树高度差绝对值不超过 1。网上很多题解写得很随意但这里有个概念陷阱就是“高度”和“深度”经常被混着用。我自己的记忆方法是深度是往下的从根到你所在节点高度是往上的从你所在节点到叶子。所以根节点的深度最大叶子节点的深度最小反过来叶子节点的高度最小约定为 1根节点的高度是整棵树的最大深度。判断一颗树是否平衡逻辑上需要先知道左右子树各自有多高再比较差值。这意味着在递归返回时你必须要得到“这棵子树到底有多高”这个数字。如果某个子树已经不平衡了还需要继续算它的高度吗不需要直接向上传递一个“失败信号”让整棵树提前结束。这个题目最容易犯的错误是想着“在每个节点用前序遍历求它的深度再比较左右孩子深度的差”。这个思路看着对但实际上你求出来的“深度”并不是该节点子树的高度而且每到一个节点都重新向下数一遍深度会带来大量重复计算。正确姿势只有一个用后序遍历求高度。2.2 递归三部曲落地用-1既当高度又当失衡标记递归不管多绕先想三件事参数和返回值是什么、终止条件是什么、单层逻辑做什么。这道题我要返回高度但还要额外表达“这颗子树已经不平衡了”。两个信息合并我的返回值就用一个 int正常情况返回高度一旦发现不平衡就返回 -1。这样上层节点拿到 -1 后立刻就能判断出整棵树已经不平衡没必要再往下朝右子树递归了。class Solution { public boolean isBalanced(TreeNode root) { return getHeight(root) ! -1; } private int getHeight(TreeNode node) { if (node null) { return 0; // 空节点高度为0 } int leftHeight getHeight(node.left); if (leftHeight -1) { return -1; // 左子树已经不平衡 } int rightHeight getHeight(node.right); if (rightHeight -1) { return -1; // 右子树已经不平衡 } // 当前节点的平衡性左右高度差不能超过1 if (Math.abs(leftHeight - rightHeight) 1) { return -1; } // 返回当前节点作为根的子树的真实高度 return Math.max(leftHeight, rightHeight) 1; } }这段代码建议亲手抄一遍再默写一遍。注意最后一行是Math.max(left, right) 1不是Math.min。这个 1 代表把当前节点自己也算进高度里这是整段递归字数最少却最容易出错的地方。2.3 提前返回的剪枝效果别把明明不平衡的子树继续算下去递归版里连续两个if (leftHeight -1) return -1;看起来多此一举实际是剪枝的精髓。我刷题时一开始偷懒省略了这两个判断心想反正最后Math.abs也会发现不平衡。但仔细一想如果左子树已经返回 -1说明左子树内部已经失衡这时候继续算右子树的高度没有任何意义纯属浪费时间。极端一点的情况是这样一颗树根节点的左子树严重失衡而右子树是节点数量极大的完全二叉树。如果不剪枝左子树发现失衡后代码还要去把右子树完整遍历一遍白白花费 O(n) 时间剪枝后左子树返回 -1 的那一刹那整个递归就一路向上退出右子树根本不会被访问到。这种“短路求值”思想在后面的回溯剪枝、动态规划优化里会反复出现越早习惯越省力。2.4 迭代思路能懂更好不懂也不影响做题递归版已经足够应付面试和笔试但面试官偶尔会追问一句“你能用迭代写吗”。迭代思路其实是用显式栈模拟后序遍历同时用一个哈希表记录每个节点的高度。基本套路是两层第一层用栈模拟“左-右-中”的后序访问顺序。遍历到中间节点时先不断把左孩子、右孩子压栈确保左右子树都处理完了才轮到中间节点。第二层每个中间节点出栈时从哈希表里查询左右子树的高度比较差值然后把当前节点的高度Math.max(left, right) 1存进哈希表。我在这里不放完整迭代代码因为后序迭代本身比较绕很容易把初学者整懵。如果你目前还在建立递归直觉优先吃透递归版等递归版熟练了再看迭代作为思维扩展。面试中能写出简洁递归并解释清楚剪枝逻辑已经能拿不错的分数。3. 257. 二叉树的所有路径前序遍历收集路径递归返回时记得撤销3.1 为什么一定要前序遍历257 题要求返回所有从根到叶子的路径比如[1-2-5, 1-3]。路径的起点永远是根顺序永远是“根在左、叶子在右”所以遍历顺序天然就是先访问根再访问左孩子再访问右孩子也就是前序遍历。中序和后序遍历都会把根节点留在中间或最后处理你想按“从根到叶子”的顺序拼接路径还得额外处理字符串顺序非常别扭。这也是一个判断经验看到“从根到叶子”这种强依赖顺序的需求优先想前序遍历。3.2 两种实现String的天然回溯 与 StringBuilder的显式回溯这道题最直观的写法是递归时传一个 String因为 Java 的 String 是不可变的每次拼接都会生成新对象天然帮你“隔离”了路径污染。class Solution { public ListString binaryTreePaths(TreeNode root) { ListString result new ArrayList(); if (root null) { return result; } dfs(root, , result); return result; } private void dfs(TreeNode node, String path, ListString result) { // 到达叶子生成一条完整路径 if (node.left null node.right null) { result.add(path node.val); return; } String nextPath path node.val -; if (node.left ! null) { dfs(node.left, nextPath, result); } if (node.right ! null) { dfs(node.right, nextPath, result); } } }这种写法的优点是思路清晰新手也好懂缺点是每层递归都会新建字符串在节点数量很大的场景下会有一定开销。但算法训练阶段先跑通逻辑比抠性能重要。用可变对象就得小心了。拿 StringBuilder 举例由于它是可变的递归返回后如果不手动“撤销”刚才追加的内容左子树残留的路径片段会污染右子树的拼接结果。private void dfs(TreeNode node, StringBuilder sb, ListString result) { // 记录进入当前节点前 sb 的长度方便退出时回退 int len sb.length(); if (len 0) { sb.append(-); } sb.append(node.val); if (node.left null node.right null) { result.add(sb.toString()); } else { if (node.left ! null) { dfs(node.left, sb, result); } if (node.right ! null) { dfs(node.right, sb, result); } } // 核心回溯恢复到进入当前节点之前的状态 sb.setLength(len); }重点看最后一行sb.setLength(len)。我在很多培训班同学的代码里见过这种 bug字符串拼接对了结果忘了回退最后输出的路径越长越长或者把左子树的节点串到了右子树路径里。如果你也遇到路径“串味”的情况十有八九是撤销没写对。3.3 边界条件空树、单节点和“1-”的干扰这道题的边界条件不多但每一个都很容易踩空树返回空列表。我在代码开头就先判了root null。只有一个根节点路径应该是1而不是1-。这个“多余的 -”是新手高频翻车点。所以拼接逻辑里我判断了len 0才加箭头保证根节点前没有-。叶子节点的判断必须严格为node.left null node.right null。只判断一边为空是不严谨的比如一个节点只有左孩子没有右孩子它不是叶子路径还必须继续走到真正的叶子。我的建议是写完代码后自己输入三个测试用例[]、[1]、[1,2,3]手算一下期望输出再跑基本能把边界问题全部暴露出来。3.4 这会是你第一次真正理解“回溯”结构回溯这个词在 257 这道题里被体现得淋漓尽致。你在 StringBuilder 里追加节点进入子树然后再递归回来把字符串缩短——这就是标准回溯模板的原型。把这段逻辑抽象一下记录当前现场 做出选择追加当前节点 递归进入下一层 撤销选择回到现场这个模板你会反复见到组合问题、排列问题、子集问题本质上都是这种“做选择-递归-撤销”的循环。所以 257 看起来只是二叉树路径题实际上是你第一次在代码里直观地看见回溯。我强烈建议你在刷完这道题后把上面的抽象模板抄在笔记里后面学回溯时会感谢今天的自己。4. 404. 左叶子之和左叶子的定义比想象中更容易绕晕4.1 “左叶子”的完整定义与两个反直觉例子“左叶子之和”听起来很简单把左叶子节点上的值加起来。但什么是左叶子必须先给它一个严谨定义这个节点是某个节点的左孩子这个节点自己没有左右孩子。有两点反直觉的地方要注意。第一一个节点即使是右子树的节点只要它是父节点的左孩子同时是叶子就算左叶子。第二根节点哪怕没有左右孩子也不算左叶子因为它没有父节点没有“左孩子”这个身份。举个容易想歪的例子7 / \ 5 6 / 8这里 8 是 6 的左孩子同时 8 自己也是叶子所以 8 是左叶子它的值应该被计入。很多人看到“左叶子”三个字下意识以为只有整棵树的左半边才算这就错了。“左”这个属性只和父节点相关和它在整棵树里的位置无关。再来一个更刁钻的1 / \ 2 3 / \ 4 54 是 2 的左孩子、是叶子计入5 是 2 的右孩子即使它是叶子也不计数。所以这一棵树的左叶子之和是 4。4.2 递归写法用父节点视角去判定孩子既然左叶子的判定依赖于“父节点”递归遍历时就别指望在访问到某个节点的时候只靠它自己判断而应该在访问父节点时检查它的左孩子。class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } int sum 0; // 当前节点的左孩子是叶子如果是直接累加 if (root.left ! null root.left.left null root.left.right null) { sum root.left.val; } // 左子树里可能还有左叶子继续递归 sum sumOfLeftLeaves(root.left); // 右子树里也可能有左叶子比如4.1里的8不能漏掉 sum sumOfLeftLeaves(root.right); return sum; } }注意最后两行左子树要递归右子树也要递归。哪怕右孩子本身是叶子如果它下面是空的递归进去返回 0但如果右子树内部存在“父节点的左孩子是叶子”的情况这部分值必须被统计到。漏递归右子树是这道题最常见的逻辑错误。还有一种更极简的写法把所有判断都浓缩进一个递归返回public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } if (root.left ! null root.left.left null root.left.right null) { return root.left.val sumOfLeftLeaves(root.right); } return sumOfLeftLeaves(root.left) sumOfLeftLeaves(root.right); }这个版本把“左孩子是左叶子”和“递归找其他左叶子”合并成一行代码更短但可读性略差。我还是推荐第一种写法因为面试时你需要边写边讲逻辑拆开更利于沟通。4.3 迭代写法栈里弹出的每个节点都可以做一次检查递归本质上是系统帮你维护了一个调用栈迭代写法无非是把它变成显式栈。用前序、中序、后序哪种都行因为这道题只需要把所有节点拜访一遍顺序不影响累加结果。public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } DequeTreeNode stack new ArrayDeque(); stack.push(root); int sum 0; while (!stack.isEmpty()) { TreeNode node stack.pop(); // 每次弹出一个节点先检查它的左孩子 if (node.left ! null node.left.left null node.left.right null) { sum node.left.val; } if (node.left ! null) { stack.push(node.left); } if (node.right ! null) { stack.push(node.right); } } return sum; }这里有个小优化点左叶子节点本身不需要再压入栈因为判断它是不是左叶子在父节点出栈时就已经完成了。真正需要继续压栈的是那些“可能含有更多左叶子”的子树。所以你可以像我上面这样先不管三七二十一左右孩子都压栈简单清晰也可以对左叶子节点额外做剪枝不把它压栈减少一次无意义的弹出。两者都正确写你顺手的。4.4 边界情况对照表场景期望结果背后的原因空树0没有节点可加只有一个根节点0根节点没有父节点不是任何人的左孩子根节点只有右孩子右孩子是叶子0右叶子不计数根节点的左孩子是叶子加左孩子值左孩子同时满足“是父亲的左孩子”和“是叶子”右子树里存在父节点的左叶子需要计入“左”只取决于父节点的左侧关系写代码前先把这个表在心里过一遍基本可以写一次就 AC。5. 222. 完全二叉树的节点个数从O(n)到O(log^2 n)的特性红利5.1 最朴素的解法任何二叉树都能数先别管“完全二叉树”这几个字把题目当成“给我任意一颗二叉树统计节点数”。这几乎是递归最入门级的题目public int countNodes(TreeNode root) { if (root null) { return 0; } return 1 countNodes(root.left) countNodes(root.right); }这行逻辑不需要动脑子当前节点算一个加上左子树的节点数再加上右子树的节点数。用层序遍历BFS也能做维护一个队列每弹出一个节点计数加 1然后把左右孩子入队。两种解法都是 O(n) 的时间复杂度。面试时先回答这个版本是稳妥的它证明你有基础能力。但面试官如果追问“这棵树除了是二叉树还是完全二叉树你能利用这个条件吗”就到了今天题单的关键部分。5.2 满二叉树公式带来的优化思路完全二叉树有一个很强的性质除了最后一层其他层都是满的而且最后一层的节点都尽可能靠左排列。这意味着对完全二叉树里的任何一个子树它有可能是满二叉树也有可能不是。怎么快速判断某棵子树是不是满二叉树看两个深度从它的左孩子出发一路朝左下走能走几步从它的右孩子出发一路朝右下走能走几步。如果两边步数相等说明左子树和右子树的最外边界高度一样——它是一棵满二叉树。满二叉树的节点数有现成公式2^h - 1其中 h 是层数。一步不用递归直接套公式。如果两边步数不相等说明这棵子树没满那就只能用老办法节点数 1 左子树节点数 右子树节点数递归往下分解。由于完全二叉树的特殊结构递归每一层都会砍掉一半“不确定区域”总体效率远高于 O(n)。5.3 递归实现与容易写错的一行位运算优化版代码如下public int countNodes(TreeNode root) { if (root null) { return 0; } int leftDepth 0; int rightDepth 0; TreeNode left root.left; TreeNode right root.right; while (left ! null) { leftDepth; left left.left; } while (right ! null) { rightDepth; right right.right; } // 如果左外边界和右外边界深度相等说明这棵子树是满二叉树 if (leftDepth rightDepth) { // 满二叉树节点数 2^(leftDepth1) - 1 return (2 leftDepth) - 1; } // 不是满二叉树递归去左右子树里继续判断 return 1 countNodes(root.left) countNodes(root.right); }这行位运算是整个代码里最容易被写错的一行。我见过很多人写成(1 leftDepth) - 1算出来的结果总是少节点。原因在于我的leftDepth是“沿最左侧走的时候经过的边的数量”不是“层数”。比如只有根节点的树走 0 条边leftDepth 0但满二叉树节点数是 1也就是2^(01) - 1 1。用位运算表达就是(2 0) - 1 1。如果写成(1 0) - 1 0根节点都被你数丢了。如果你对位运算不熟用Math.pow(2, leftDepth 1) - 1效果完全一样只是稍慢。我不建议为了炫技而用位运算前提是你真明白2 x的含义。5.4 复杂度对比与二分思路的一句话说明普通递归复杂度 O(n)优化版复杂度 O(log^2 n)。怎么估算的每调用一次递归就会在两个 while 循环里沿边界往下走这一步是 O(log n)而递归的深度最多也是 O(log n)——因为完全二叉树的树高是对数级的。两个 O(log n) 相乘就是 O(log^2 n)。举一个直观的数字假设树里有 10 亿个节点普通递归要真的访问 10 亿个节点优化版大约只需要几千次操作。这个差距在极端测试数据下是肉眼可见的。力扣官方还有一种更进阶的解法先确定树的高度再二分最后一层的节点数量用位掩码验证某个编号对应的节点是否存在。思路很漂亮但训练营阶段能把“满二叉树直接套公式”这个优化想明白已经超过了大多数刷题者。我这里不展开先把基础优化吃透。6. 四道题刷完我总结的二叉树递归检查清单6.1 递归三部曲在这四道题上的映射如果要把今天四道题浓缩成一张思维地图那它们就是在反复回答三个问题。第一这个函数该返回什么。110 返回子树高度并用 -1 表达“不平衡”257 不需要返回具体值只需要把路径写进结果集404 返回左叶子之和222 返回节点个数。返回值定了递归的骨架就定了。第二什么时候停下来。树的递归几乎无一例外第一反应永远是“空节点怎么处理”。110 里空节点返回 0257 里空节点直接 return404 里空节点返回 0222 里空节点返回 0。然后再考虑真正的“终结条件”比如 257 的叶子节点要把路径收集进结果集。第三单层逻辑做什么。这个最灵活110 在单层比较高度差257 在单层拼接路径404 在单层判断左孩子是否为叶子222 在单层判断是否为满二叉树。单层逻辑写对了递归基本成功了一大半。6.2 一张表记住四道题的易错点题目核心遍历方式返回值/状态最高频易错点110 平衡二叉树后序遍历int 高度-1 表示失衡混淆高度深度忘了剪枝257 二叉树的所有路径前序遍历无返回值收集结果StringBuilder 忘记回溯多出“-”404 左叶子之和任意遍历整型累加和漏递归右子树根节点误判为左叶子222 完全二叉树节点个数后序 特性判断int 节点数满二叉树公式里的 1 写错位运算搞混这张表我建议抄在解题笔记里刷题中期拿出来复习一遍比再刷十道新题更有用。尤其是 257 的“回溯”和 222 的“满二叉树公式”是训练营同学互相提问时最容易翻车的地方。6.3 最后一件事把“为什么”讲清楚第十五天刷完我最大的体会是二叉树的递归题从来不靠背题而是靠把“遍历顺序、返回值、边界条件”这三个问题想清楚。四道题看起来各自独立其实是同一套思维在四个场景下的反复演练。所以如果今天你也刚好刷到这里别急着去做下一批题目。先把每道题的代码遮住口头给自己讲一遍“110 为什么用后序257 为什么用前序404 为什么可以随便用任何顺序222 的满二叉树公式为什么是 2 的 h 次方减 1”这几个问题能流利答出来今天的四道题才算真正消化了。后面遇到的二叉树递归题大概率都是这些套路的变形而已。