OJ-leetcode-235. 二叉搜索树的最近公共祖先（简单二叉搜索树）

悠悠 2022-12-10 15:53 154阅读 0赞

**目录**

题目

思路

代码

结果

优秀题解

提升笔记

--------------------

# 题目 #

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树:  root = \[6,2,8,0,4,7,9,null,null,3,5\]

示例 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, 因为根据定义最近公共祖先节点可以为节点本身。

![f6e46ace5976ecb7788e718bdedf3e62.png][] 示例树

说明:

所有节点的值都是唯一的。  
    p、q 为不同节点且均存在于给定的二叉搜索树中。  
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree

# 思路 #

两个指针向给定的两个值寻找，保存值，分叉就停止。

## 代码 ##

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            TreeNode* temp_p = root;
            TreeNode* temp_q = root;
            TreeNode* ancestor = root;
            // 有一个找到就停止
            while(temp_p->val!=p->val&&temp_q->val!=q->val)
            {
                // 向p、q移动
                if(p->val<temp_p->val)temp_p=temp_p->left;
                else temp_p=temp_p->right;
                //cout<<temp_p->val<<endl;
                if(q->val<temp_q->val)temp_q=temp_q->left;
                else temp_q=temp_q->right;
                //cout<<temp_q->val<<endl;
                // 保存公共祖先,分叉停止
                if(temp_p->val==temp_q->val)ancestor = temp_p;
                else break;
            }
            return ancestor;
        }
    };

## 结果 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][] 结果

# 优秀题解 #

[三行递归解法][Link 1]

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

# 提升笔记 #

1.递归写法简单空间占的过多

2.递归转循环也是不错的办法

相关题目

[2019北邮研究生复试题（第二题）][2019]

更多内容：[OJ网站题目分类，分难度整理笔记（leetcode、牛客网）][OJ_leetcode]

喜欢本文的请动动小手点个赞，收藏一下，有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[f6e46ace5976ecb7788e718bdedf3e62.png]: /images/20221123/f9a92d1b779744de8dbc8c6e2d6f4064.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70]: /images/20221123/f0c335fc25414bb592a05acdc0b6aac6.png
[Link 1]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/solution/c-di-gui-jie-fa-by-hdlugjqzc5/
[2019]: https://blog.csdn.net/lady_killer9/article/details/88940771
[OJ_leetcode]: https://blog.csdn.net/lady_killer9/article/details/108273799