###### tags: `LeetCode` `Tree` `Easy`
# LeetCode #235 [Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)
### (Easy)

---
給定一個二元搜索樹, 找到該樹中兩個指定節點的最近公共祖先。

最近公共祖先的定義為：“對於有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”

---
由於是二元搜尋樹, 因此左子節點會小於根節點, 右子節點會大於根節點。

而當一節點在左子樹而另一節點在右子樹時, 其共同祖先為左右子樹的交會節點, 因此只要找到在哪個節點開始, 目標兩節點分別在該節點的左右子樹即可。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root||(p->val>root->val&&q->val<root->val)||(p->val<root->val&&q->val>root->val))return root;
        while((root->val-p->val)*(root->val-q->val)>0)
            root=root->val>p->val?root->left:root->right;
        return root;
    }
};