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

我们从root开始判断，只有两种情况可以得到结果：

• 当前节点的值等于p或q其中一个
• 当前节点的值在p和q之间

如果以上都不满足，说明两个节点都在root的一边，我们判断一下root值和p值（或q值）的大小：

• 如果都比root大，root往右边走一格
• 如果都比root小，root往左边走一格

c++实现

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if(p == root->val || q == root->val) return root->val;  //有root直接返回
        if(p > root->val && q < root->val) return root->val;  //root两边各一个的也直接返回
        if(q > root->val && p < root->val) return root->val;
        
        if(q > root->val){
            return lowestCommonAncestor(root->right, p, q);
        }else{
            return lowestCommonAncestor(root->left, p, q);
        }
    }
};

python实现

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
        # write code here
        if q == root.val or p == root.val:
            return root.val
        elif p < root.val < q:
            return root.val
        elif q < root.val < p:
            return root.val
        else:
            if q > root.val:
                return self.lowestCommonAncestor(root.right, p, q)
            else:
                return self.lowestCommonAncestor(root.left, p, q)