0235. Lowest Common Ancestor of a Binary Search Tree ==================================================== 题目信息 -------- :题号: 0235 :难度: Medium :主题: 二叉搜索树、最近公共祖先、树 :原题: `LeetCode 0235 `_ :重点: 返回原树节点、祖先允许包含节点自身、BST 值序关系、p 与 q 保证存在 题目重述 -------- 给定一棵二叉搜索树的根节点 ``root``,以及树中两个不同节点 ``p``、``q``,返回它们的最近公共祖先。公共祖先是同时位于 ``p`` 和 ``q`` 的祖先链上的节点;“最近”表示深度最大。按照题目定义,一个节点可以是它自己的祖先。 树中节点数位于 ``[2, 10^5]``,节点值位于 ``[-10^9, 10^9]`` 且互不相同。输入保证 ``p``、``q`` 都是树中已有节点并且 ``p != q``。返回值必须是原树中的对应节点引用,而不是仅返回同值整数或新建节点;树结构无需修改。 自建示例 -------- 两个节点位于同一侧: .. code-block:: text 输入:root = [10, 5, 15, 2, 7, 12, 18],p = 节点 2,q = 节点 7 输出:节点 5 解释:节点 5 的子树同时包含 2 和 7,而它的任一更深后代都不能同时包含二者。 其中一个节点就是祖先: .. code-block:: text 输入:root = [10, 5, 15, 2, 7],p = 节点 5,q = 节点 7 输出:节点 5 解释:题目允许节点作为自己的祖先;5 同时是自身和 7 的祖先,因此它就是最近公共祖先。 利用 BST 的分流位置 ------------------ 在当前节点 ``root`` 处比较 ``p->val`` 和 ``q->val``: * 两者都小于当前值,最近公共祖先只能在左子树,向左走; * 两者都大于当前值,最近公共祖先只能在右子树,向右走; * 否则两者分居当前节点两侧,或其中一个就是当前节点,当前节点就是最近公共祖先。 这里返回的是当前树节点指针,而不是创建一个同值节点。节点值互不相同,所以值比较足以确定方向; 题目保证两个目标都在树中,搜索不会走到空指针。 正确性说明 ---------- 若两个目标都在当前节点同一侧,当前节点不可能是它们的最近公共祖先,因为另一侧没有目标, 而 BST 的值序关系保证目标的公共祖先仍在该侧。若它们分侧,任何从当前节点向下的子树至多包含其中一个, 当前节点首次同时覆盖两者,正是最深的公共祖先;目标等于当前节点时同样成立。 C++ 实现 -------- .. code-block:: cpp class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while (root != nullptr) { if (p->val < root->val && q->val < root->val) { root = root->left; } else if (p->val > root->val && q->val > root->val) { root = root->right; } else { return root; } } return nullptr; } }; 代码分析 -------- 每次循环沿一条根到叶路径下降,时间复杂度为 ``O(h)``,额外空间为 ``O(1)``;平衡树为 ``O(log n)``, 退化树最坏为 ``O(n)``。代码只读取值和指针,不改变树结构,返回的指针仍指向原树节点。