二叉树递归四题拆解：返回值、遍历顺序与回溯技巧-北京尧图网络

1. 第15天二叉树刷到这里该抓什么1.1 从会递归到会设计递归这四道题刚好是阶梯如果你正在跟代码随想录算法训练营走到第15天差不多就该和二叉树硬碰硬了。我今天的任务单是力扣 110、257、404、222 四道题。说实话这四道题放在同一天刷安排得非常讲究它们表面上都是二叉树递归套路实际上各自的返回类型、遍历顺序、是否回溯、是否利用树的结构特性完全不一样。如果你只是机械地背递归模板很容易出现代码能跑但换个题就不会的情况。这四道题分别是平衡二叉树判断、二叉树的所有路径、左叶子之和、完全二叉树的节点个数。它们适合正在刷力扣二叉树专题的人也适合准备面试前集中补递归基础的人。读完这篇你应该能清楚回答三个问题什么时候用前序、什么时候用后序递归函数到底该返回什么为什么有些递归需要回溯而有些不需要代码随想录的训练营节奏是一天一刷、按专题递进到了二叉树这个阶段最重要的不是把某道题的代码背下来而是理解递归的数据流动方向。110 是自底向上汇总信息257 是自顶向下记录路径404 是站在父节点视角做条件判断222 是利用树的结构特性直接剪枝。四种玩法恰好对应面试里递归题的大部分考点。1.2 一张地图看懂四道题的考核点在动手写代码之前先把四道题的差异列出来。我学算法有一个习惯同一批题优先看它们的不同而不是相同。这四道题如果只用一个维度区分就是递归的返回类型和遍历顺序题号核心考点推荐遍历顺序递归返回什么是否需要回溯110子树高度差后序int高度或 -1不需要257路径收集前序void结果存外部需要404左叶子判定后序/前序均可int累加值不需要222完全二叉树性质后序int节点个数不需要盯着这个表看三分钟你会发现一个规律凡是需要从子树拿信息往上传递的题110、404、222都用后序遍历凡是需要从上往下走并记录路径的题257用前序遍历。遍历顺序不是玄学它取决于数据流动的方向。子树信息往上汇总就必须先把左右子树算完再处理中间节点路径信息往下传递就必须先处理中间节点再进入左右子树。1.3 刷题前的整体提醒根据我自己的刷题经验这四道题最容易踩的坑有三个第一110 题把高度和深度混为一谈导致递归的状态设计出错第二257 题忘记递归和回溯成对出现路径列表越攒越长第三404 题没有意识到左叶子的判定必须站在父节点视角否则根本找不到判断依据。至于 222 题坑比较隐蔽——很多人只知道暴力遍历却不知道完全二叉树存在 O(log n * log n) 的解法。接下来我按题目逐个拆解每道题都会给出完整代码、复杂度分析和我实测下来的坑。2. 力扣110高度与深度一对被混淆的兄弟2.1 为什么第一反应必须是后序遍历求高度力扣 110 判断平衡二叉树的定义很直接每个节点的左右子树高度差不超过 1。但高度和深度这两个概念很多人刷题时根本没分清。深度是从根节点往下数越往下越深高度是从叶子节点往上数越往上越高。递归函数如果把求深度和求高度混着写代码就会乱成一片。平衡性判断依赖的是子树的高度信息。当前节点要判断自己是否平衡必须先知道左右子树的高度再比较差值。这种先知道孩子再处理自己的顺序天然就是后序遍历左右中。前序遍历做不到因为访问当前节点时还没拿到子树信息你只能先把当前节点判断完再往下走等走到叶子再往回回溯信息逻辑绕一大圈。我建议在草稿纸上画一棵三层的不平衡树亲手标一遍每个节点的高度你会发现高度值一定是先算孩子再算父亲。这个从下往上的方向决定了代码里的递归结构先递归 left再递归 right最后处理 mid 的逻辑。2.2 用 -1 做提前出局标记避免重复计算标准解法是在后序遍历求高度的同时做判断。递归函数返回当前子树的高度如果发现某棵子树不平衡直接返回 -1。父节点拿到 -1 之后不再往下计算因为整棵树已经注定不平衡了。这有点像竞赛里的一票否决制只要有一个子问题不满足条件后面就不用算了。代码Javaclass 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); if (leftHeight -1) { return -1; } int rightHeight getHeight(node.right); if (rightHeight -1) { return -1; } if (Math.abs(leftHeight - rightHeight) 1) { return -1; } return Math.max(leftHeight, rightHeight) 1; } }这里有几个值得注意的细节空节点高度为 0叶子节点高度为 1这个约定和力扣对高度的判定完全一致。每次递归先检查左右子树是否已经返回 -1这既是剪枝也避免在无效子树上浪费时间。当前节点的高度是左右子树最大高度加 1注意不是两者之和是最大值加 1。提示如果递归函数里每次都调用一个独立的 height 函数去重新计算子树高度整体复杂度会退化到 O(n^2)。正确做法是在一次后序遍历里同时完成求高度和判平衡两件事。2.3 复杂度分析时间复杂度 O(n)每个节点只访问一次空间复杂度是递归栈深度平衡树为 O(log n)斜树退化为 O(n)。这个写法的核心优势是单次遍历避免了每个节点都当根节点算一次子树高度的重复计算。我之前犯过的一个错是先写一个 getHeight然后在主函数里对每个节点都调用 isBalanced 和 getHeight。看起来逻辑正确但遇到链式斜树每一层都在重新扫描整棵子树力扣上直接超时。后来才发现-1 标记法不是优化技巧而是这类自底向上问题的标配写法。面试官如果问你能不能一次遍历完成判断你给他讲 -1 的传递逻辑这题基本稳过。3. 力扣257路径收集的本质是回溯3.1 前序遍历为什么是路径题的默认选项257 题要求输出从根到所有叶子节点的路径比如[1-2-5, 1-3]。路径是有顺序的从根节点开始一路往叶子走中间经过的节点按访问顺序排列。二叉树里能按根 - 左 - 右顺序输出自然序列的遍历方式就是前序遍历。假设我们站在一个节点上要把这个节点加进当前路径然后继续往下走。先记录中间节点再分别去左孩子和右孩子最后把路径串起来——这个动作天然就是前序。如果你用中序或者后序路径里的节点顺序就不对了。路径本身就是一条从根到叶的访问序列前序遍历的顺序和路径的语义完全吻合。很多题解会说这题用回溯但回溯不是一个独立的技术它是前序遍历过程中撤销选择的动作。你往前走了一步记录了这个节点回到岔路口的时候必须把这一步撤销否则路径里会混入不属于当前分支的节点。3.2 回溯必须与递归成对出现这题真正的难点不在遍历而在路径的现场恢复。想象你正在走迷宫手里拿着一张纸记录走过的节点。走到叶子时把纸上内容抄一份放进结果集然后要回到上一个岔路口这时必须把最后写的那个节点划掉。划掉动作就是回溯。递归里如果path.add(node.val)出现在函数开头那么path.remove(path.size() - 1)必须在递归返回后执行。我把代码写成了进入节点时 add递归回来 remove的方式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); } } }注意第三个细节递归函数里先 add 了当前节点如果走到叶子直接 return。这里 return 之后回溯由调用方的 remove 完成。根节点是唯一的例外它没有父节点调用但整个 traversal 结束时 path 里还剩根节点不过那时函数已经全部返回不影响 result。提示注意递归和回溯必须成对出现——每个 add 一定对应一个 remove否则 path 会残留不属于当前分支的节点。3.3 终止条件遇到叶子而不是 node null很多人写二叉树递归习惯了node null就 return但这题不能这么写。如果终止条件是 node null那走到叶子之后还会再往左右空孩子各调用一次路径会被重复记录而且需要额外判断空节点时不能 add。正确做法是遇到叶子左右孩子都为空就记录并返回因为路径只在叶子处结束。还有一个常见的 Java 坑ListInteger不能直接用String.join(-, path)必须手动遍历拼接。如果你想让代码更简洁可以把 path 换成ListString每个节点存字符串但那样每次递归都会构造新字符串内存开销大一点。我在面试时通常不用这种做法因为面试官更想看到可撤销的路径维护。3.4 List 引用共享是另一个隐藏考点Java 里 path 是引用传递。你在递归里往 path 里 add 元素返回后如果不 removepath 会越来越长结果全乱。这题我在训练营里看到不少同学翻车症状是输出的路径越来越长或者所有路径都带上之前分支的尾巴。Python 也有同样的问题。如果用 list 作为 path不手动复制或删除一样会互相污染。Python 的解法里常见path [node.val]这种写法本质是每次递归生成新列表用空间换回溯的简单性。两种写法各有取舍但你要清楚自己写的到底是原地修改还是新建副本别混着用。4. 力扣404左叶子之和判定条件全在父节点身上4.1 一个左叶子的正确打开方式左叶子的定义是它是叶子节点左右孩子都为空并且它是父节点的左孩子。这个定义里有两条信息缺一不可节点本身是叶子以及它在父节点眼中的位置是左。如果直接在递归里判断当前节点是左孩子吗你会发现做不到因为你无法从当前节点得知自己是谁的孩子。所以这题要反过来想站在父节点的视角检查它的左孩子是不是叶子。翻译成代码如果当前节点的左孩子不为空并且左孩子的左孩子和右孩子都为空那么当前节点的左孩子就是一个左叶子它的值应该被累加。这一点就是 404 题和前面几道题最大的区别判断条件不在自己身上而在爸爸身上。很多新手在这一题上卡住不是不会写递归而是找错了判断的视角。4.2 完整题解后序递归版本我用的写法是后序遍历的框架先递归左右子树再处理当前节点作为父节点时能贡献的左叶子值。因为累加操作没有顺序依赖所以前序、中序、后序都正确但后序结构最清晰也方便和 110、222 题的思路统一起来。class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } int leftValue sumOfLeftLeaves(root.left); int rightValue sumOfLeftLeaves(root.right); int midValue 0; if (root.left ! null root.left.left null root.left.right null) { midValue root.left.val; } return midValue leftValue rightValue; } }这里midValue是当前节点作为父节点时的左叶子贡献leftValue和rightValue是左右子树内部所有左叶子的和。三个部分加总就是整棵树的答案。有一个细节需要注意如果整棵树只有一个根节点根不是任何节点的左孩子所以答案为 0。上面的代码里root.left 为 nullmidValue 为 0左右子树递归结果也是 0正确。如果 root 本身就是空树直接返回 0 也对。4.3 为什么是左孩子就加会翻车最容易错的写法是遍历每个节点只要发现 node.left ! null就把 node.left.val 加上。这会把左非叶子节点也加进去。举个例子根节点只有一个左孩子这个左孩子下面又挂着右子树那 root.left 不是叶子但它会被错误累加。反过来也不能只在递归里判断当前节点是不是叶子因为叶子不一定是左孩子。比如一个节点是右孩子但它没有孩子那它是右叶子不应该计入。所以必须由父节点来认领左叶子。如果喜欢层序遍历也可以队列弹出一个节点时检查它的左孩子是否存在且是否为叶子是则累加然后正常把左右孩子入队。这个版本更直观但空间复杂度比递归大好在题目数据量小两种都能过。我个人更推荐递归版因为面试时能顺势讲清楚父节点视角这个关键点。5. 力扣222完全二叉树的节点个数优化点藏在性质里5.1 暴力遍历也能过但不是考察意图222 题第一眼很简单数节点。递归后序遍历每个节点访问一次累加即可class Solution { public int countNodes(TreeNode root) { if (root null) { return 0; } return countNodes(root.left) countNodes(root.right) 1; } }时间复杂度 O(n)。力扣上这题用这个写法能过。但如果你在面试被问面试官为什么给你一个完全二叉树而不是普通二叉树就要意识到这题的进阶考点利用完全二叉树的性质把复杂度降到 O(log n * log n)。题目描述明确说这个树是完全二叉树这个条件不会是白给的。什么是完全二叉树除了最后一层其他层都是满的最后一层的节点从左到右连续排列中间没有空缺。这个结构限制给了我们一个普通二叉树没有的数学性质。5.2 满二叉树公式2 的 h 次方减 1完全二叉树有一个特点如果某棵子树的最左深度和最右深度相等那么这棵子树就是满二叉树。满二叉树的节点个数公式是 2 的 h 次方减 1其中 h 是层数或者用边数表示。有了这个公式一棵满子树不用遍历直接算出节点数然后接到剩下的递归结果里。对完全二叉树而言从任意节点出发它的左子树和右子树中至少有一棵是满二叉树。这是因为完全二叉树的节点是从左到右连续排列的最后一层只有最右侧可能缺节点。所以计算一次从左孩子一路向左的最左深度、以及从右孩子一路向右的最右深度只要它们相等立刻用公式返回不等就继续向左右递归同时把当前节点计入。代码如下class Solution { 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) { return (2 leftDepth) - 1; } return countNodes(root.left) countNodes(root.right) 1; } }注意leftDepth 和 rightDepth 都是从 0 开始计数的边数。当边数相等时说明这棵子树是满二叉树节点数为 2 的 (leftDepth 1) 次方减 1在代码里用(2 leftDepth) - 1实现。位运算避免了浮点误差也比Math.pow快。5.3 位运算视角完全二叉树的节点编号如果还想再深一步完全二叉树还有一个很强的性质从根节点开始根编号为 1左孩子编号是父节点编号的 2 倍右孩子编号是父节点编号的 2 倍加 1。这个规则在二进制下看就是向左走等于原二进制末尾加 0向右走等于末尾加 1。因此一个节点从根到它的路径可以直接编码成一个二进制数。基于这个编号规则可以用二分查找判断某个编号的节点是否存在从而算出最后一层的节点数总复杂度同样是 O(log n * log n)。这种方案在力扣题解里也有但日常刷题我更推荐上面的减治写法好理解、代码短、也容易在面试的白板上写出来。位运算属于进阶延伸知道原理即可不一定要作为主解法去写。提示不要用Math.pow(2, depth) - 1浮点数在大深度下可能产生精度问题。2 leftDepth的整数位运算更可靠。5.4 复杂度对比写法时间复杂度空间复杂度什么时候用普通后序递归O(n)O(log n) ~ O(n)通用不要求利用性质满二叉树公式减治O(log n * log n)O(log n)树是完全二叉树时每次递归都需要沿最左、最右走到底一次是 O(log n)递归深度是 O(log n)所以乘起来是 O(log n * log n)。这个复杂度比 O(n) 小很多尤其节点数量大的时候优势明显。刷题过程中我也见过另一种思路层序遍历数节点但那样需要额外队列空间而且完全没有用到完全二叉树的信息面试时不够加分。6. 四道题合起来看递归三部曲的三种变体6.1 递归三部曲在四道题里的映射代码随想录里反复讲的递归三部曲是确定递归函数的参数和返回值、确定终止条件、确定单层递归逻辑。这四道题放在一起正好是三部曲的三种变体。110 的返回值是 int 高度靠 -1 传递不平衡终止条件是空节点返回 0单层逻辑是左右子树高度比较。257 的返回值是 void结果放在外部 list 里终止条件是叶子节点单层逻辑是前序访问并维护 path。404 的返回值是 int 累加值终止条件是空节点返回 0单层逻辑是父节点视角累加左叶子值。222 的返回值是 int 节点数终止条件是空节点返回 0以及满二叉树直接套公式的剪枝。可以看到三部曲不是一套死公式。参数和返回值决定了数据怎么流动终止条件决定了什么时候停止单层逻辑决定了遍历顺序。每次写递归前先把这三个问题在草稿纸上写一遍比直接上手敲代码有效得多。6.2 一张表看穿返回值、终止条件和遍历顺序我整理了一张总结表列了四道题的关键设计方便你二刷时对照维度110257404222遍历顺序后序前序后序/前序均可后序递归返回值int 高度voidint 累加int 计数终止条件空节点叶子节点空节点空节点/满二叉树回溯无有无无关键技巧-1 标记List 引用回溯父节点判定2^h - 1 公式这个表值得贴在刷题日记里。面试前最后一天只看这个表就能把四道题的骨架全部回忆起来。你会发现递归题的变化其实很少先想清楚返回值是给父节点用的还是给最终答案用的再想清楚当前节点需要什么信息。6.3 我的排坑清单和刷题顺序建议最后说点实操层面的体会。这些题我刷的时候踩过不少坑挑几个最有代表性的110 题不要在主函数里写一个求高度的函数再对每个节点调用一遍判断平衡。那样每棵子树会被重复求高度遇到斜树直接超时。必须用后序遍历加 -1 标记一次遍历搞定。257 题Java 里如果 path 用字符串path - node.val直接拼接可以不用回溯但每次递归都会生成新字符串代码更简洁。如果面试追求空间效率用 List 加回溯更稳。关键是别两种写法混着来。404 题递归进入左子树时不要在子树内部判断我是不是左叶子因为子树内部没有我是父亲左孩子这个信息会漏加或错加。222 题最左深度不等于最右深度时不要继续用公式必须往左右递归递归到子树满足条件才能收敛。这个减治思路理解后完全二叉树的很多问题都能同理优化。刷题顺序上我建议先做 110 和 404这两题帮你巩固返回值设计再做 257练习回溯最后做 222理解题目给的性质不是装饰。如果你也在跟训练营或者自己刷力扣这里是我个人最有用的一个建议每做完一道题在题号旁边写一行字——这题的递归返回了什么为什么是这个遍历顺序写够二十题你会发现递归真的入门了。第 15 天不是终点二叉树后面还有一大串但这四道题打下的底子后面很多题都会用到。尤其是 110 的-1 传递和 222 的满二叉树公式一个处理判断型递归一个处理结构优化这两个思路往后做二叉搜索树、公共祖先、序列化题目时你会反复遇到。

二叉树递归四题拆解：返回值、遍历顺序与回溯技巧

相关推荐

B/S架构原理到实践：从HTTP请求到Django落地全解析

Node.js生态融合实战：用Aspire打通JavaScript与底层系统

基于SpringBoot+Vue的流浪动物救助平台：全栈项目源码实战解析

更多资讯

Linux显示驱动调试工具全解析：从dmesg到IGT的实战指南

AI日报系统设计：从需求定义到可复现落地

PLC开关量传感器全解析：光电、接近、磁性、光纤放大器选型接线与调试

桶访问日志还在路上？别等了，两条日志链路现在就能接

内景地铁站内部

AI应用上下文管理实战：从窗口大小到context-mode策略

今日更新

Agent Skills 完全指南：原理、写法、安装与实战避坑

Agent Skills 实战：从 Genkit 定义到 GKE 部署与排查

Agent Skills 实战：从设计到调试的完整指南

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？