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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    int fun(TreeNode *r,int n1,int n2)
    {
        if(r->val>=n1 && r->val<=n2)
            return r->val;
        if(r->val>=n2)  //祖先在左侧
            return fun(r->left,n1,n2);             
        else            //祖先在右侧
            return fun(r->right,n1,n2);  
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if(p>q)
        {
            int temp = p;
            p=q;
            q=temp;
        }
        return fun(root,p,q);
    }
};

第一步先将p和q按小大顺序交换位置

然后进入递归判断

根据排序二叉树的性质，小值在左子树，大值在右子树

我们可以明确找到结束递归的条件就是当

root->val >= p && root->val<= q，此时root就是最近祖先

为什么呢？经过简单的逻辑分析可以知道，某个节点能将p和q两个节点区分在左右子树上，这个节点就是最近的祖先

而后我们交给下级任务，直至完成。

因为测试条件的特殊性，我们不需要考虑越界问题。