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

1.先获取遍历到所取数值的序列，然后比较两个序列最远相同的数，即其最近公共祖先

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    
    
    void find(TreeNode* root, int m,vector<int> &res)
    {
        if(!root)
            return ;
        res.push_back(root->val);
        if(m == root->val)
            return;
        else if(m > root->val)
            find(root->right,m,res);
        else
            find(root->left,m,res);
    }

    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        vector<int> res1;
        vector<int> res2;
        find(root,p,res1);
        find(root,q,res2);
        int result = 0;
        int n = min(res1.size(),res2.size());
        for(int i = 0;i<n;++i)
        {
            if(res1[i] == res2[i])
                result = res1[i];
        }
        return result;

    }
};

2.使用递归

思路：

我们也可以利用二叉搜索树的性质：对于某一个节点若是p与q都小于等于这个这个节点值，说明p、q都在这个节点的左子树，而最近的公共祖先也一定在这个节点的左子树；若是p与q都大于等于这个节点，说明p、q都在这个节点的右子树，而最近的公共祖先也一定在这个节点的右子树。而若是对于某个节点，p与q的值一个大于等于节点值，一个小于等于节点值，说明它们分布在该节点的两边，而这个节点就是最近的公共祖先，因此从上到下的其他祖先都将这个两个节点放到同一子树，只有最近公共祖先会将它们放入不同的子树，每次进入一个子树又回到刚刚的问题，因此可以使用递归。

具体做法：

• step 1：首先检查空节点，空树没有公共祖先。
• step 2：对于某个节点，比较与p、q的大小，若p、q在该节点两边说明这就是最近公共祖先。
• step 3：如果p、q都在该节点的左边，则递归进入左子树。
• step 4：如果p、q都在该节点的右边，则递归进入右子树。

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