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

方法一：搜索路径比较

得到两个目标值在二叉搜索数的路径，对两个路径进行比较，最后一个相同的结点就是最近的公共祖先

时间复杂度：o(n)

空间复杂度：o(n)。需要辅助队列存储路径

class Solution {
  public:
    //获取从根节点到目标值的路径
    queue<TreeNode*> getPath(TreeNode* root, int target) {
        queue<TreeNode*> res;
        while (root->val != target) {
            res.push(root);
            if (target > root->val)
                root = root->right;
            else
                root = root->left;
        }
        res.push(root);
        return res;
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        //得到两个目标值在二叉树的路径
        queue<TreeNode*> q1 = getPath(root, p);
        queue<TreeNode*> q2 = getPath(root, q);

        TreeNode* pub;
        //最后一个相等的结点就是最近的公共祖先
        while (!q1.empty() && !q2.empty()) {
            if (q1.front() == q2.front())
                pub = q1.front();
            q1.pop();
            q2.pop();
        }
        return pub->val;
    }
};

方法二：递归

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
  public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
	  	//如果当前结点与目前值相同，则当前就是最近的公共祖先
        if (root->val == p || root->val == q)
            return root->val;
		//如果遍历到当前结点，两个目标值需要分别走向左右子树，则当前就是最近的公共祖先
        if ((root->val > p && root->val < q) ||
            (root->val < p && root->val > q))
            return root->val;
	  	//继续向下遍历寻找最近的公共祖先
        else if (root->val > p && root->val > q)
            return lowestCommonAncestor(root->left, p, q);
        else
            return lowestCommonAncestor(root->right, p, q);
    }
};