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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param p int整型 
 * @param q int整型 
 * @return int整型
 */
 //方法：递归
 //判断树是否为空，空则返回-1(因为函数返回值要求是整型int)，否则进行下一步
 //三种情况
 //1、如果两个数，一个小于根节点的值，一个大于根节点的值，那么这两个数位于根节点的两侧，则根节点为最近公共祖先
 //2、如果两个数均小于根节点的值，即两个数位于根节点左边，应当递归传入当前根节点的左儿子
 //3、如果如果两个数均大于根节点的值，即两个数位于根节点右边，应当递归传入当前根节点的右儿子
 //4、其他特殊情况，比如两个数所在节点，一个是父节点，一个是子节点

int lowestCommonAncestor(struct TreeNode* root, int p, int q )
{
    // write code here
    //判断树是否为空，空则返回-1(因为函数返回值要求是整型int)，否则进行下一步
    if(!root)
    {
        return -1;
    }
    
    //三种情况
    //1、如果两个数，一个小于根节点的值，一个大于根节点的值，那么这两个数位于根节点的两侧，则根节点为最近公共祖先
    if((p<root->val && q>root->val) || (p>root->val && q<root->val))
    {
        return root->val;
    }

    //2、如果两个数均小于根节点的值，即两个数位于根节点左边，应当递归传入当前根节点的左儿子
    else if((p<root->val && q<root->val) )
    {
        return lowestCommonAncestor(root->left, p, q);
    }

    //3、如果如果两个数均大于根节点的值，即两个数位于根节点右边，应当递归传入当前根节点的右儿子
    else if((p>root->val && q>root->val) )
    {
        return lowestCommonAncestor(root->right, p, q);
    }

    //4、其他特殊情况，比如两个数所在节点，一个是父节点，一个是子节点
    else 
    {
        return root->val;
    }
}