# 235. Lowest Common Ancestor of a Binary Search Tree

> ***View the book with <i class="fa fa-book"></i> Book Mode.***

- [**LeetCode筆記目錄**](https://hackmd.io/@WeiYee/SyABdj_eA)

## :book: 題目

**網址:** https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

## :dart: 解題步驟
- 使用遞迴，拿 p、q 和 當前節點 value 比較
- p、q 皆小於 root.val -> 代表 p、q 都在左子樹，還需要繼續從左子樹往下尋找
- p、q 皆大於 root.val -> 代表 p、q 都在右子樹，還需要繼續從右子樹往下尋找
- 其餘情況，例如: p、q 一個在左子樹一個在右子樹 、 p、q 至少一個為當前節點，代表當前節點即為所求

## :pencil: 程式碼
### Java

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int rootValue = root.val;
        if (p.val < rootValue && q.val < rootValue) return lowestCommonAncestor(root.left, p, q);
        if (p.val > rootValue && q.val > rootValue) return lowestCommonAncestor(root.right, p, q);
        return new TreeNode(rootValue);
    }
}