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

/**
 * 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
        //这种限制的数据结构（不能使用双亲指针），就需要想其他办法。
        //在树中求路径是一种常见的做法，难点在于记录路径，这道题好在是二叉搜索树，路径无需遍历搜索
        vector<int> pp, qq;
        TreeNode *pr = root, *qr = root;
        while(pr){
            pp.push_back(pr->val);
            if(pr->val<p)   pr = pr->right;
            else if(pr->val>p) pr = pr->left;
            else break;
        }
        while(qr){
            qq.push_back(qr->val);
            if(qr->val<q)   qr = qr->right;
            else if(qr->val>q)  qr = qr->left;
            else break;
        }
        int res = root->val;
        int len = min(pp.size(), qq.size());
        for(int i = 0; i < len; ++i){
            if(pp[i]==qq[i]){
                res = pp[i];
            }
            else break;
        }
        return res;
    }
};

方法一：

一般找最近公共节点我们都是采用双亲指针往上溯，但是这道题限制了数据结构，只有左右指针，因此我们要考虑另觅它法。

最开始我希望能够使用递归的方式到每一个树上去判断是否同时包含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
        while (root) {//空树的情况题目没说明返回值所以不处理，可以直接返回root->val
            if (p < root->val && q < root->val) {
                if (root->left) {
                    root = root->left;
                } else break;
            } else if (p > root->val && q > root->val) {
                if (root->right) {
                    root = root->right;
                } else break;
            } else break;//说明分叉了或者一个已经找到了
        }
        return root->val;
    }
};

方法二：

这个方法主要是要对树的结构和遍历方式有清晰的认识，和二叉树搜索树后序遍历判断是否正确遍历一样，关键在掌握遍历方向。

对于每个公共祖先节点，这两个节点在这个根节点所控制的树上，若是不在这个树上就不是公共节点。

每次往下走都是往左或者往右，如果一个往左一个往右那么下一个节点就不是它们的公共节点了。

因此最后一个公共祖先一定是让它们分开或者走到头了。

在最后公共节点之前的节点因为是在一棵树上，所以两个节点每次选择的方向都会一致。

由此可知我们只要一直往下走直到两个方向开始分叉或者完结就得到最近公共祖先。