剑指 Offer 68 - II 二叉树的最近公共祖先：递归回溯法深度解析（附 Python / Java / C++ 实现）

剑指 Offer 68 - II 二叉树的最近公共祖先递归回溯法深度解析附 Python / Java / C 实现【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读本文围绕 LeetCode-Book 仓库《剑指 Offer 68 - II. 二叉树的最近公共祖先》官方题解展开系统讲解普通二叉树非二叉搜索树中最近公共祖先Lowest Common AncestorLCA的递归求解思路先给出祖先与最近公共祖先的形式化定义再拆解后序遍历回溯过程中的四种返回值情况并给出 Python、Java、C 三种语言的精简写法与四情况展开写法。同时结合仓库内sword_for_offer/codes/下的可运行源码与测试用例验证算法的正确性与复杂度边界。读完本文你将掌握自底向上回溯这一二叉树高频面试套路并能独立写出任意二叉树 LCA 的递归实现。一、问题定义什么是祖先与最近公共祖先题目要求给定一个二叉树非二叉搜索树和两个节点p、q找出它们的最近公共祖先。本题对应 剑指 Offer 68 - II. 二叉树的最近公共祖先.md与 LeetCode 236 为同一道题仓库另有对应题解 236. 二叉树的最近公共祖先.md。祖先的定义若节点p在节点root的左右子树中或p root则称root是p的祖先。注意这里祖先包含节点自身。最近公共祖先的定义设节点root为节点p, q的某个公共祖先若其左子节点root.left和右子节点root.right都不是p, q的公共祖先则称root是最近的公共祖先。直观理解从根节点出发p和q的公共祖先形成一条从根向下的祖先链这条链上最深的那个节点就是最近公共祖先。二、最近公共祖先的三种可能情况根据上述定义若root是p, q的最近公共祖先则只可能为以下情况之一p和q在root的子树中且分列root的异侧即分别在左、右子树中p root且q在root的左或右子树中q root且p在root的左或右子树中。也就是说要么p、q一个在左子树一个在右子树此时交点汇合点就是root要么其中一个节点本身就是另一个节点的祖先。三、核心思路后序遍历 自底向上回溯本题不能像二叉搜索树版本剑指 Offer 68 - I. 二叉搜索树的最近公共祖先.md那样利用节点值大小关系定向搜索因为普通二叉树没有任何有序性可利用只能遍历整棵树。解法采用递归对二叉树进行遍历先递归处理左、右子树再根据子树返回的结果判断当前节点——这本质上是后序遍历先左、再右、后处理当前节点。当遇到节点p或q时向上一层返回该节点从底至顶回溯过程中一旦发现p, q分列某个节点root的异侧则root即为最近公共祖先向上返回root即可。这个向上传递结果的过程保证了最先满足左右子树各命中一个目标的节点一定是深度最深的那个公共祖先即最近公共祖先。四、递归解析终止条件、递推工作与返回值1. 终止条件当越过叶节点root为null直接返回null表示该分支未找到p或q当root p或root q直接返回root表示在该分支命中了目标节点。2. 递推工作开启递归左子节点返回值记为left开启递归右子节点返回值记为right。3. 返回值根据left和right展开为四种情况情况leftright含义返回值1空空root的左、右子树中都不包含p, qnull2非空非空p, q分列root异侧root即最近公共祖先root3空非空p, q都不在左子树中right4非空空p, q都不在右子树中left其中情况3.又可细分为两种子情形p, q其中一个在root的右子树中此时right指向p假设为p即p是q的祖先p就是最近公共祖先p, q两节点都在root的右子树中此时right指向的是右子树中已经回溯求出的最近公共祖先节点。情况4.与情况3.完全对称。观察发现情况1.可合并进情况3.和4.内当left为空时无论right是否为空都返回rightnull也自然被返回因此精简代码可以只写两次判空详见下文代码。五、复杂度分析时间复杂度 O(N)其中N为二叉树节点数最差情况下例如p, q都位于最深的叶节点需要递归遍历树的所有节点空间复杂度 O(N)最差情况下二叉树退化为链表递归深度达到N系统调用栈使用 O(N) 大小的额外空间。六、三种语言的代码实现6.1 精简写法情况 1 合并入 3、4Pythonclass Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: if not root or root p or root q: return root left self.lowestCommonAncestor(root.left, p, q) right self.lowestCommonAncestor(root.right, p, q) if not left: return right if not right: return left return rootJavaclass Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode 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) return right; if(right null) return left; return root; } }Cclass Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root nullptr || root p || root q) return root; TreeNode *left lowestCommonAncestor(root-left, p, q); TreeNode *right lowestCommonAncestor(root-right, p, q); if(left nullptr) return right; if(right nullptr) return left; return root; } };6.2 四情况展开写法class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: if not root or root p or root q: return root left self.lowestCommonAncestor(root.left, p, q) right self.lowestCommonAncestor(root.right, p, q) if not left and not right: return # 1. if not left: return right # 3. if not right: return left # 4. return root # 2. if left and right:class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode 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 null; // 1. if(left null) return right; // 3. if(right null) return left; // 4. return root; // 2. if(left ! null and right ! null) } }class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root nullptr || root p || root q) return root; TreeNode *left lowestCommonAncestor(root-left, p, q); TreeNode *right lowestCommonAncestor(root-right, p, q); if(left nullptr right nullptr) return nullptr; // 1. if(left nullptr) return right; // 3. if(right nullptr) return left; // 4. return root; // 2. if(left ! null and right ! null) } };七、仓库源码验证可运行用例与工具函数LeetCode-Book 仓库为本题提供了完整可运行的 Python / Java / C 实现与驱动代码Python 精简版sfo_68ii_the_nearest_common_ancestor_of_a_binary_tree_s1.py、展开版sfo_68ii_the_nearest_common_ancestor_of_a_binary_tree_s2.pyJavasfo_68ii_the_nearest_common_ancestor_of_a_binary_tree_s1.java含 s2Csfo_68ii_the_nearest_common_ancestor_of_a_binary_tree_s1.cpp含 s27.1 测试用例剖析仓库源码中的测试树按层序数组表示为[3, 5, 1, 6, 2, 0, 8, None, None, 7, 4, ...]对应的树形结构为3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4用例一p 5q 15在左子树、1在右子树分列根节点3的异侧因此最近公共祖先为3用例二仓库 s2 展开版同用例同样查询5与1展开版代码命中情况2.left、right均非空返回root。从代码可见驱动流程先用list_to_tree/vectorToTree/TreeNode.arrToTree将层序数组还原为二叉树再用get_tree_node按值定位p、q节点指针最后调用lowestCommonAncestor并打印res.val。运行 Python 版用例的输出为3与预期一致。7.2 依赖的公共工具函数上述驱动代码依赖仓库统一的二叉树工具模块它们定义了TreeNode结构、数组建树与按值取节点等基础能力读者可自行查阅Pythoninclude/binary_tree.py 中list_to_tree(arr)通过层序遍历队列将数组还原为树get_tree_node(root, val)通过先序递归查找指定值的节点并返回其引用Java / C 版本分别位于 java/include 与 cpp/include 目录。7.3 与 BST 版本Offer 68 - I的对比二叉搜索树版剑指 Offer 68 - I可利用root.val与p.val、q.val的大小关系定向下降时间复杂度 O(log N)最差 O(N)代码更短普通二叉树版本题没有有序性可依赖必须遍历最差 O(N)其 LeetCode 236 对应题解及多解法可参考 236. 二叉树的最近公共祖先.md仓库在selected_coding_interview/codes/下还提供了该题的多种语言实现如 python/lc_236_lowest_common_ancestor_of_a_binary_tree_s1.py。八、总结本题的递归解法抓住了一个关键不变式后序遍历回溯时任何节点向上返回的要么是已找到的最近公共祖先要么是命中的 p 或 q。当某个节点的左右返回值同时非空说明p, q首次在该节点两侧汇合该节点就是答案。理解这一递推语义后精简版代码中的两次判空也就水到渠成面试时既可以直接给出 O(N) 时间、O(N) 空间的最优递归解也能流畅解释四种情况背后的推理过程。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考