教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文以《算法通关手册》中的 0235. 二叉搜索树的最近公共祖先题解 为骨架讲解如何利用二叉搜索树BST的有序性在O(n)时间内找到两个指定节点的最近公共祖先Lowest Common AncestorLCA并给出完整可运行的 Python 实现、复杂度分析以及它与普通二叉树 LCA 解法的区别。读完本文你将掌握「利用 BST 性质剪枝搜索路径」这一核心技巧并能在面试中快速给出最优解。一、题目概述题目链接0235. 二叉搜索树的最近公共祖先 - 力扣题目标签树、深度优先搜索、二叉搜索树、二叉树难度中等1.1 题目大意给定一个二叉搜索树的根节点root以及两个指定节点p和q要求找到该树中两个指定节点的最近公共祖先。1.2 关键概念定义在求解之前必须先明确题目中两个核心概念的定义这也是面试中常被追问的边界条件祖先Ancestor如果节点p在节点node的左子树或右子树中或者p node则称node是p的祖先。最近公共祖先Lowest Common AncestorLCA对于树的两个节点p、q最近公共祖先表示为一个节点lca_node满足lca_node是p、q的祖先且lca_node的深度尽可能大。一个节点也可以是自己的祖先——这条规则正是示例 2 中答案可以等于p本身的依据。1.3 题目约束所有节点的值都是唯一的。p、q为不同节点且均存在于给定的二叉搜索树中。1.4 示例示例 1输入: root [6,2,8,0,4,7,9,null,null,3,5], p 2, q 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。示例 2输入: root [6,2,8,0,4,7,9,null,null,3,5], p 2, q 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。示例 2 非常关键节点2是节点4的祖先4位于2的右子树中同时2 p因此根据「一个节点也可以是自己的祖先」的定义最近公共祖先就是节点2本身。二、前置知识二叉搜索树的性质本题能高效求解的根本原因在于二叉搜索树的有序性。根据 docs/05_tree/05_04_binary_search_tree.md 中的定义二叉搜索树Binary Search Tree, BST满足以下三条性质对于任意节点如果其左子树非空则左子树所有节点的值均小于该节点的值对于任意节点如果其右子树非空则右子树所有节点的值均大于该节点的值任意节点的左右子树也都分别是二叉搜索树递归定义。一句话概括即左子树所有节点值 根节点值 右子树所有节点值。正是基于这一性质当我们从根节点出发查找某个值时每经过一个节点都可以确定性地排除一半的搜索范围——要么进入左子树要么进入右子树绝无第三种可能。这个「定向选择子树」的能力正是二叉搜索树查找、插入、删除等操作平均O(log n)的根基见 docs/05_tree/05_04_binary_search_tree.md 中关于查找算法的分析。三、核心思路寻找两条路径的「分岔点」对于节点p、节点q最近公共祖先就是从根节点分别到它们路径上的分岔点也是这两条路径中最后一个相同的节点。理解这一句话即可抓住本题的本质从根节点出发到p有一条路径到q也有一条路径两条路径在前半段必然重合都从根节点开始然后在某个节点处分道扬镳这个分岔点就是最近公共祖先。现在我们的问题就是求这个分岔点。在普通二叉树中求这个分岔点需要遍历整棵树并回溯比较但在二叉搜索树中由于节点值的全局有序性我们可以在每一步遍历时仅凭当前节点值与p.val、q.val的大小关系就确定两条路径的下一个节点是否相同从而直接锁定分岔点。3.1 递归遍历的判定规则从根节点root开始遍历每一步遵循以下三条规则如果当前节点的值大于p、q的值即ancestor.val p.val and ancestor.val q.val说明p和q都应该在当前节点的左子树中因此将当前节点移动到它的左子节点继续遍历如果当前节点的值小于p、q的值即ancestor.val p.val and ancestor.val q.val说明p和q都应该在当前节点的右子树中因此将当前节点移动到它的右子节点继续遍历如果当前节点不满足上面两种情况则说明p和q分别在当前节点的左右子树上或者其中一个节点就是当前节点本身则当前节点就是分岔点直接返回该节点即可。为什么第三种情况可以确定返回需要分三种子情况分析p、q分别在当前节点的左、右子树中当前节点显然是两条路径的分岔点p 当前节点此时q必在左子树或右子树中根据「节点可以是自己的祖先」当前节点就是 LCAq 当前节点同理当前节点就是 LCA。而由于题目保证p ! q第三种情况不可能出现p q 当前节点的矛盾情形所以上述判定是完备且无歧义的。3.2 完整代码class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: ancestor root while True: if ancestor.val p.val and ancestor.val q.val: ancestor ancestor.left elif ancestor.val p.val and ancestor.val q.val: ancestor ancestor.right else: break return ancestor这段代码有几点值得注意的细节循环终止条件代码使用while True 显式break。由于题目保证p、q均存在于树中且节点值唯一分岔点一定存在因此循环必然终止不存在死循环风险。单指针迭代整个算法只维护一个ancestor指针从root出发逐步下移不需要额外的栈、数组或哈希表来记录路径。与 0236 的通用解法对比本题与 0236. 二叉树的最近公共祖先 是姊妹题。0236 的二叉树没有有序性约束必须递归遍历左右子树、收集两侧的搜索结果再向上合并左右子树都不为空时返回当前根节点其空间复杂度为O(n)递归栈深度而本题利用 BST 性质只沿一条确定的方向下探空间开销为常数。可见「数据结构的有序性」直接改变了算法的最优复杂度。3.3 复杂度分析时间复杂度O(n)其中n是二叉搜索树的节点个数。最坏情况下如树退化为单链表且p、q位于链尾指针需要从根节点一路移动到叶子节点此时遍历了树高个节点而退化为链表时树高为n故上界为O(n)。空间复杂度O(1)。算法仅使用一个指针变量ancestor没有递归调用栈也没有任何辅助数据结构空间开销与节点数量无关。3.4 进一步分析平均情况的复杂度需要补充说明的是上述O(n)是最坏情况上界。从二叉搜索树的性质看见 docs/05_tree/05_04_binary_search_tree.md 的查找算法分析当树接近完全平衡时树高为h log₂n每次比较后搜索范围减半此时实际下探的节点数约为O(log n)。只有当 BST 退化为单链表例如按升序插入构建的树时才会退化到O(n)。因此在平均情况下本题的实际运行时间远优于最坏上界。四、模拟运行以示例 1 演示算法流程以示例 1 的输入为例root [6,2,8,0,4,7,9,null,null,3,5]p 2q 8逐步模拟ancestor 66 2且6 8不成立6 8。6 2且6 8不成立。进入else返回节点 6。再看p 2q 4示例 2ancestor 66 2且6 4成立 → 移动到左子节点2ancestor 22 2不成立2 2不成立。进入else返回节点 2。此时p自身即为分岔点符合「节点可以是自己的祖先」的定义。再举一个需要向下走两步的例子p 3q 5均在节点4的左右子树中ancestor 66 3且6 5成立 → 移动到左子节点2ancestor 22 3且2 5不成立2 3且2 5成立 → 移动到右子节点4ancestor 44 3且4 5不成立4 3且4 5不成立。进入else返回节点 43、5分别位于4的左右子树4正是分岔点。从模拟过程可以看到指针每走一步就根据 BST 的有序性排除掉一整棵子树因此算法天然地「沿着两条路径共同的方向」前进一旦两条路径将要分开立即终止。五、仓库中的相关资源《算法通关手册》仓库中与本题直接相关的资源如下便于读者按图索骥深入学习本题题解原文docs/solutions/0200-0299/lowest-common-ancestor-of-a-binary-search-tree.md即本文所依据的骨架文档。姊妹题二叉树的最近公共祖先0236docs/solutions/0200-0299/lowest-common-ancestor-of-a-binary-tree.md对比阅读可加深对「BST 有序性如何降低复杂度」的理解。0236 使用递归后序遍历需要遍历整棵树并向上合并左右子树结果时间O(n)、空间O(n)。同源题LCR 193. 二叉搜索树的最近公共祖先docs/solutions/LCR/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof.md其解题思路与代码与本题完全一致可作为刷题巩固难度标记为简单。二叉搜索树基础教程docs/05_tree/05_04_binary_search_tree.md包含 BST 的查找、插入、创建、删除全流程的算法步骤与 Python 代码以及复杂度对比表是理解本题前置性质的最佳阅读材料。题目分类索引二叉搜索树题目完整列表见 docs/00_preface/00_06_categories_list.md 的「二叉搜索树题目」小节本题0235与 0098 验证 BST、0700 搜索、0701 插入、0450 删除、0426 BST 转双向链表等共同构成 BST 专项练习序列全部题目索引另见 docs/00_preface/00_05_solutions_list.md。需要说明的是仓库中的算法源码目录codes/python/目前主要覆盖数组、链表、栈队列、字符串、树线段树/树状数组/并查集、图、动态规划等模块的完整实现如codes/python/05_tree/下的tree_unionFind.py、tree_segmentTree_update_point.py等而 LeetCode 题解以 Markdown 文档形式沉淀在docs/solutions/目录中本文的代码可直接复制用于 LeetCode 提交。六、总结与面试要点本题是二叉搜索树系列的高频面试题掌握程度可以从三个层次检验能写出迭代解法利用 BST 有序性单指针下探时间O(n)平均O(log n)、空间O(1)即本文给出的解法能讲清终止条件为什么当前节点值介于p.val、q.val之间或等于其中之一时可以直接返回——因为此时两条路径已分岔或已到达p/q自身这正是「分岔点」的定义能对比普通二叉树 LCA0236说明为什么 0236 需要递归合并左右子树结果、空间O(n)而本题凭借 BST 有序性可以做到空间O(1)体现对数据结构特性的理解深度。面试中常见的追问还包括如果树退化为单链表怎么办回答复杂度退化为O(n)但算法正确性不受影响如果p、q不一定存在怎么办回答本题约束保证二者均存在若需处理不存在情形则要先做存在性校验思路会相应改变。建议将本题与 0236. 二叉树的最近公共祖先、LCR 193. 二叉搜索树的最近公共祖先 三题对照复习形成完整的 LCA 解题体系。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐gh_mirrors/ha/haha核心原理HprofParser如何解析Android堆转储文件gh_mirrors/ha/haha核心原理HprofParser如何解析Android堆转储文件 GitHub 加速计划ha/haha是一个用于自动化分AlgoNote 算法通关手册LeetCode 0270「最接近的二叉搜索树值」二分查找解法全解析AlgoNote 算法通关手册LeetCode 0270「最接近的二叉搜索树值」二分查找解法全解析 导读 本文基于 AlgoNote 开源算法学习仓库中的题解教程文档知识库LeetCode 面试题 04.08 首个共同祖先二叉树最近公共祖先LCA的递归解法全解析LeetCode 面试题 04.08 首个共同祖先二叉树最近公共祖先LCA的递归解法全解析 本篇技术指南聚焦于 doocs/leetcode 仓库中《程序示例工程教程上一篇learn-harness-engineering 第十一讲把 agent 的运行时与评估过程做进 harness 的可观测性设计下一篇Pinia 备忘清单深度解析Vue 状态管理从安装、Store 到持久化与测试jaywcjlove/reference创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考