LeetCode题目之腾讯精选练习（50题）：二叉搜索树的最近公共祖先

雨点打透心脏的1/2处 2024-04-19 08:12 31阅读 0赞

# 题目 #

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

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

例如，给定如下二叉搜索树: root = \[6,2,8,0,4,7,9,null,null,3,5\]  
![在这里插入图片描述][20190915172931227.png]

**示例 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, 因为根据定义最近公共祖先节点可以为节点本身。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

**说明** :

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

## 算法实现 ##

public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)//递归法
    {
        
        int pVal = p.val;
        int qVal = q.val;
        int parentVal = root.val;
        if (pVal > parentVal && qVal > parentVal)
            return LowestCommonAncestor(root.right, p, q);
        else if (pVal < parentVal && qVal < parentVal)
            return LowestCommonAncestor(root.left, p, q);
        else
            return root;
    }

## 执行结果 ##

**执行结果** : 通过  
**执行用时** : 152 ms, 在所有 C\# 提交中击败了85.96%的用户  
**内存消耗** : 30.8 MB, 在所有 C\# 提交中击败了7.69%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

## 迭代法 ##

public TreeNode LowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q)//迭代法
    {
        
        int pVal = p.val;
        int qVal = q.val;
        TreeNode node = root;
        int parentVal;
        while (node != null)
        {
        
            parentVal = node.val;
            if (pVal > parentVal && qVal > parentVal)
                node = node.right;
            else if (pVal < parentVal && qVal < parentVal)
                node = node.left;
            else
                break;
        }
        return node;
    }

![在这里插入图片描述][20190915173352859.png]

## 小的总结 ##

本次题目自己先设计算法，但没有成功，后来看了题解，原来是没有搞清楚二叉搜索树的特性，如下：  
![在这里插入图片描述][20190915173733300.png]  
在看完题解的思路后，编写了代码。

[20190915172931227.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/425584e4e1b3427f9e2e7d31ccb28e25.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/0f7596540ce148dbaec4b1b00ac224f0.png
[20190915173352859.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/fe670b3e63e04dc586203c7b1bb6e596.png
[20190915173733300.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c0c18ddda92a4650b06e660bb177d588.png