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。返回值必须是原树中的对应节点引用,而不是仅返回同值整数或新建节点;树结构无需修改。

自建示例

两个节点位于同一侧:

输入:root = [10, 5, 15, 2, 7, 12, 18],p = 节点 2,q = 节点 7
输出:节点 5
解释:节点 5 的子树同时包含 2 和 7,而它的任一更深后代都不能同时包含二者。

其中一个节点就是祖先:

输入:root = [10, 5, 15, 2, 7],p = 节点 5,q = 节点 7
输出:节点 5
解释:题目允许节点作为自己的祖先;5 同时是自身和 7 的祖先,因此它就是最近公共祖先。

利用 BST 的分流位置

在当前节点 root 处比较 p->val 和 q->val:

  • 两者都小于当前值,最近公共祖先只能在左子树,向左走;

  • 两者都大于当前值,最近公共祖先只能在右子树,向右走;

  • 否则两者分居当前节点两侧,或其中一个就是当前节点,当前节点就是最近公共祖先。

这里返回的是当前树节点指针,而不是创建一个同值节点。节点值互不相同,所以值比较足以确定方向; 题目保证两个目标都在树中,搜索不会走到空指针。

正确性说明

若两个目标都在当前节点同一侧,当前节点不可能是它们的最近公共祖先,因为另一侧没有目标, 而 BST 的值序关系保证目标的公共祖先仍在该侧。若它们分侧,任何从当前节点向下的子树至多包含其中一个, 当前节点首次同时覆盖两者,正是最深的公共祖先;目标等于当前节点时同样成立。

C++ 实现

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)。代码只读取值和指针,不改变树结构,返回的指针仍指向原树节点。