【leetcode235】二叉搜索树的最近公共祖先

迈不过友情╰ 2022-11-16 15:22 169阅读 0赞

## 题目描述 ##

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

**说明:**

*  所有节点的值都是唯一的。
 *  p、q 为不同节点且均存在于给定的二叉搜索树中。

**示例：**

> 输入: root = \[6,2,8,0,4,7,9,null,null,3,5\], p = 2, q = 4  
> 输出: 2  
> 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

![在这里插入图片描述][20210407225627458.png_pic_center]

## 解题思路 ##

对于二叉树的问题，我们通常要往递归的思路上去思考。思考递归的关键在于找到子问题，和终止条件。

在本题中子问题是：对于一个根节点，

*  如果节点p和节点q 都在左子树上，那么应该到左子树上去寻找最近公共祖先；
 *  如果节点p和节点q都在右子树上，那么应该到右子树上去寻找最近公共祖先；
 *  如果节点p和节点q 一个在左子树节点，一个在右子树节点，那么根节点就是最近公共祖先。

终止条件是：对于一个根节点，

*  如果根节点为空，那么就返回空，说明没找到任何一个节点。
 *  如果根节点的值与任何一个节点的值相等，就返回根节点，表示找到了其中一个节点。

以上是二叉树, 找到该树中两个指定节点的最近公共祖先的思路。

那么对于二叉搜索树，要明白**二叉搜索树的特点：**

> 若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；
> 
> 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
> 
> 它的左、右子树也分别为二叉搜索树

根据这个性质，我们想判断节点p和节点q 是不是在根节点的左子树上，只需要将节点p和节点q 的值和根节点的值进行比较即可。

class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            
            if(root->val < p->val && root->val < q->val){
                return lowestCommonAncestor(root->right, p, q);
            }else if(root->val > p->val && root->val > q->val){
                return lowestCommonAncestor(root->left, p, q);
            }else{
                return root;
            }
        }
    };

**复杂度分析**

*  时间复杂度：因为二叉树的节点有且只会被访问一次，因此时间复杂度为 O(N)。
 *  空间复杂度：递归本质上使用是系统栈，栈的深度取决于二叉树的高度。在最坏情况下二叉树为一条链，此时高度为 N，因此空间复杂度为 O(N)。

class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            TreeNode* res = root;
            while(res){
                if(res->val > p->val && res->val > q->val){
                    res = res->left;
                }else if(res->val < p->val && res->val < q->val){
                    res = res->right;
                }else{
                    break;
                }
            }
            return res;
        }
    };

**复杂度分析**

*  时间复杂度：因为二叉树的节点有且只会被访问一次，因此时间复杂度为 O(N)。
 *  空间复杂度：没有使用辅助的栈，因此空间复杂度为 O(1)。

[20210407225627458.png_pic_center]: /images/20221022/cc1170c131c947b981b2b9b95771fc08.png