最小公共祖先

1. LeetCode 235. Least Common Ancestor of a Binary Search Tree

2. 描述

给定一个二叉搜索树，找出两个给定节点的最小公共祖先。

3. 解决方案 1：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root == nullptr){
        return nullptr;
    }
    
    if((root->val <= p->val && root->val >= q->val)||
     (root->val >= p->val && root->val <= q->val) ){
        return root;
    }else if(root->val >= p->val && root->val >= q->val){
        return lowestCommonAncestor(root->left,p,q);
    }else{
        return lowestCommonAncestor(root->right,p,q);
    }
}

4. 解决方案 2：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root->val > p->val && root->val > q->val){
        return lowestCommonAncestor(root->left,p,q);
    }else if(root->val < p->val && root->val < q->val){
        return lowestCommonAncestor(root->right,p,q);
    }else{
        return root;
    }
}

##　5. 解决方案 3：迭代法

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* cur = root;
    while(true){
        if(cur->val < p->val && cur->val < q->val){
            cur = cur->right;
        }else if(cur->val > p->val && cur->val > q->val){
            cur = cur->left;
        }else{
            return cur;
        }
    }
}