题解 | #二叉搜索树的最近公共祖先#

二叉搜索树有个特点：左子树和右子树都是二叉搜索树，且左儿子雄安与根节点小于右儿子。

根据这个特点，如果两个值分别子啊根节点两侧，那根节点就是共同祖先；如果都小于根节点，那

酒啊在左子树里找，反之在右子树里找

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param p int整型 
 * @param q int整型 
 * @return int整型
 */
int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    // write code here
    struct TreeNode *cur = root;
    if(cur->val > p && cur->val > q){
        cur = cur -> left;
        return lowestCommonAncestor(cur,  p,  q);
         
    }
    else if(cur->val < p && cur->val < q){
        cur = cur -> right;
        return lowestCommonAncestor(cur, p,  q);
    }
    else{
        return cur -> val;
    }
}