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

这题和上一题JZ86不一样。

虽然JZ86的方法是通用的方法，但是我们要针对这道题给出的多的条件进行优化，从而达到最优的算法（不然这二叉搜索树的条件不是白给了）。

对于二叉搜索树而言，它一定是节点的左子树都小于该节点，右节点都大于该节点。

所以，我们要利用这个条件 $m i n n < = r o o t - > v a l < = m a x n$ ,满足这个条件的，最下层的节点，就是我们要搜索的节点。

但这有一个例外。

如果p节点的祖先是q呢？

如果我们不考虑这个情况，一味地取最下层满足条件的节点作为答案，我们则会取成p节点作为答案，而非正确答案q节点。

因此，我们要特殊判断这个情况。

if (root->val != minn && root->val != maxn) ans = root;

c++
python

/**
 * 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整型
     */
    TreeNode* ans = nullptr;
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        int minn = min(p, q);
        int maxn = max(p, q);
        
        findP(root, minn, maxn);
        return ans->val;
    }
    
    void findP(TreeNode* root, int minn, int maxn) {
        if (!root) return;
        if (root->val >= minn && root->val <= maxn) {
            if (!ans) ans = root;
            else {
                if (root->val != minn && root->val != maxn) ans = root;
            }
        }
        
        if (root->val <= minn) {
            findP(root->right, minn, maxn);
        }
        
        else if (root->val >= maxn) {
            findP(root->left, minn, maxn);
        }
        return;
    }
};

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param p int整型 
# @param q int整型 
# @return int整型
#
class Solution:
    ans = None
    def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
        # write code here
        minn = min(p, q)
        maxn = max(p, q)
        self.findP(root, minn, maxn)
        return self.ans.val
    
    
    def findP(self, root, minn, maxn):
        if not root:
            return
        if root.val >= minn and root.val <= maxn:
            if not self.ans:
                self.ans = root
            else:
                if root.val != minn and root.val != maxn:
                    self.ans = root
        if root.val <= minn:
            self.findP(root.right, minn, maxn)
        elif root.val >= maxn:
            self.findP(root.left, minn, maxn)
        return