# 235. Lowest Common Ancestor of a Binary Search Tree (E)

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the [definition of LCA on Wikipedia](https://en.wikipedia.org/wiki/Lowest_common_ancestor): “The lowest common ancestor is defined between two nodes `p` and `q` as the lowest node in `T` that has both `p` and `q` as descendants (where we allow **a node to be a descendant of itself**).”

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png)

```
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png)

```
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
```

**Example 3:**

```
Input: root = [2,1], p = 2, q = 1
Output: 2
```

 

**Constraints:**

* The number of nodes in the tree is in the range `[2, 105]`.
* `-109 <= Node.val <= 109`
* All `Node.val` are **unique**.
* `p != q`
* `p` and `q` will exist in the BST.

### Solution:

<https://www.jiuzhang.com/solution/lowest-common-ancestor-of-a-binary-search-tree/>

#### 解题思路

* 这道题与[88. 最近公共祖先](https://www.lintcode.com/problem/lowest-common-ancestor-of-a-binary-tree/description)相似，都是求树内两个节点的最近公共祖先（LCA），我们本题也继续采用深度优先搜索（DFS）的方法。
* 不同的是，这道题明确指出这是二叉搜索树（BST），我们复习一下BST的性质：
  * 对任意节点N，左子树上的所有节点的值都小于等于节点N的值
  * 对任意节点N，右子树上的所有节点的值都大于等于节点N的值
  * BST的左子树和右子树也都是 BST
* 我们如果在搜索时充分利用BST的性质，就能够有效剪枝。

#### 算法流程

1. 从根节点`root`开始，遍历整棵树
2. 如果`root`等于`p`或`q`，那么`root`即为`p`和`q`的LCA。
3. 如果`root`同时大于`p`和`q`，说明`p`和`q` 都在左子树上，那么将`root.left`作为根节点，继续第一步的操作。
4. 如果`root`同时小于`p`和`q`，说明`p`和`q` 都在右子树上，那么将`root.right`作为根节点，继续第一步的操作。
5. 如果以上情况都不成立，说明`p`和`q`分别在两颗子树上，那么`root`就是`p`和`q`的LCA。

#### 复杂度分析

* 时间复杂度：O(N)，其中 N 为 BST 中节点的个数。在最坏的情况下，BST退化成链表，我们可能访问 BST 中所有的节点。
* 空间复杂度：O(N)，其中 N 为 BST 中节点的个数。所需开辟的额外空间主要是递归栈产生的，在最坏的情况下，BST退化成链表，那么递归栈的深度就是BST的节点数目。

```
public class Solution {
    /**
     * @param root: root of the tree
     * @param p: the node p
     * @param q: the node q
     * @return: find the LCA of p and q
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // root 等于 p或q
        if (root == p || root == q){
            return root;
        }
        // p, q 都在左子树
        if (p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        // p, q 都在右子树
        if (p.val > root.val && q.val > root.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        // p, q 分别在左右子树，那么root即为结果
        return root;
    }
```