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

目录前言一、路径总和 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; } }小白秒懂逻辑这就是从下往上 “冒泡” 结果。只要左右各找到一个当前节点就是它们的交汇点。代码极简、无冗余、面试直接默写。三、两道题核心思想总结路径总和 III题型双重递归、路径搜索关键词任意起点、向下延伸、long 防溢出口诀每个节点当起点递归向下凑总和最近公共祖先题型后序遍历、递归回溯关键词左右判断、最近公共节点口诀后序左右找两边都有就是祖先