当前位置：首页 > news >正文

递归封神！二叉树两大究极考题：路径总和 III + 最近公共祖先｜面试原地 AC

news 2026/6/4 16:17:05

前言

一、路径总和 III：任意起点、任意终点的路径计数

思路一句话总结

完整 AC 代码

关键点小白精讲

二、二叉树的最近公共祖先：后序遍历的神级应用

思路一句话总结

完整 AC 代码

小白秒懂逻辑

三、两道题核心思想总结

路径总和 III

前言

二叉树最能拉开差距的，就是递归思想。今天这两道题，一道是任意路径求和（高频易错），一道是最近公共祖先（递归模板题）。它们不考复杂数据结构，只考你对递归、回溯、后序遍历的理解。全文思路直白、代码干净，适合直接收藏背模板。

一、路径总和 III：任意起点、任意终点的路径计数

这道题最大特点：路径不需要从根开始，也不需要在叶子结束，只要从上到下即可。很多人卡在用 int 溢出、递归边界不清，我直接给你能 AC、防溢出、最稳写法。

思路一句话总结

以每一个节点作为起点，向下递归寻找路径和为 targetSum 的条数。
两层递归：1）遍历树中每个节点（充当起点）2）从该节点向下 DFS，累加统计满足条件的路径
关键点：必须用 long 避免数值溢出

完整 AC 代码

java

运行

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { /** * 深度优先：以每个节点为起点，向下寻找满足条件的路径 * 最终总和 = 当前节点贡献 + 左子树贡献 + 右子树贡献 */ public int pathSum(TreeNode root, int targetSum) { if (root == null) return 0; // 当前节点作为起点的路径数 int res = rootSum(root, (long) targetSum); // 递归处理左右子树 res += pathSum(root.left, targetSum); res += pathSum(root.right, targetSum); return res; } /** * 从 node 出发，向下寻找和为 targetSum 的路径条数 * 使用 long 防止 int 溢出 */ public int rootSum(TreeNode node, long targetSum) { int res = 0; if (node == null) return 0; long val = node.val; // 当前节点值正好匹配，找到一条路径 if (val == targetSum) { res++; } // 继续向左右子树寻找，目标和减去当前值 res += rootSum(node.left, targetSum - val); res += rootSum(node.right, targetSum - val); return res; } }

关键点小白精讲

为什么用 long？测试用例会给极大数，int 相加会溢出变负数，导致错误判断。
两层递归结构清晰一层遍历所有起点，一层向下延伸路径。
边界干净空节点直接返回 0，不做多余判断。

二、二叉树的最近公共祖先：后序遍历的神级应用

这道题是面试必考模板，代码短到离谱，但思想极经典。核心就是：后序遍历 + 左右结果判断祖先位置。

思路一句话总结

采用后序遍历：先左、再右、最后处理根。
如果当前节点是 p 或 q，直接返回它。
如果左右子树都返回非空，说明 p、q 分别在两侧，当前节点就是祖先。
如果一侧非空一侧空，说明目标都在非空那一侧，返回那一侧即可。

完整 AC 代码

java

运行

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { /** * 后序递归：从下往上找最近公共祖先 */ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 递归出口：空节点 或 找到 p/q，直接返回 if (root == null || root == p || root == q) { return root; } // 左子树查找 TreeNode left = lowestCommonAncestor(root.left, p, q); // 右子树查找 TreeNode right = lowestCommonAncestor(root.right, p, q); // 左右都找到了 → 当前节点就是最近公共祖先 if (left != null && right != null) { return root; } // 哪边不为空，祖先就在哪边 return left != null ? left : right; } }