# 235. 二叉搜索树的最近公共祖先

## Link

{% embed url="<https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/>" %}

## Problem

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

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

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

![](https://1992890748-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F0qYY1ILl1K1crNjGMFmh%2Fuploads%2FGy2HILtmLUIKn7TV8NR2%2Fimage.png?alt=media\&token=3eeac755-2dc0-4ef4-98fa-a9d1a37a951d)

示例 1：

{% code overflow="wrap" %}

```
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是6
```

{% endcode %}

示例2：

{% code overflow="wrap" %}

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

{% endcode %}

提示：

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

## Solution

{% tabs %}
{% tab title="Go" %}

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	out := root
    for {
        if p.Val > out.Val && q.Val > out.Val{
            out = out.Right
        }else if p.Val < out.Val && q.Val < out.Val{
            out = out.Left
        }else{
            break
        }
    }
    return out
}
```

{% endtab %}

{% tab title="C++" %}

```cpp
```

{% endtab %}

{% tab title="Rust" %}

```rust
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn lowest_common_ancestor(root: Option<Rc<RefCell<TreeNode>>>, p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let val_p = p.unwrap().borrow().val;
        let val_q = q.unwrap().borrow().val;
        let mut root = Rc::clone(root.as_ref().unwrap());
        loop {
            let val_root = root.borrow().val;
            if val_root > val_p && val_root > val_q {
                let left = Rc::clone(root.borrow().left.as_ref().unwrap());
                root = left;
            } else if val_root < val_p && val_root < val_q {
                let right = Rc::clone(root.borrow().right.as_ref().unwrap());
                root = right;
            } else {
                break Some(root);
            }
        }
    }
}
```

{% endtab %}
{% endtabs %}