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

递归

三种情况：

• 当前结点值小于q，p，就在当前结点的左子树寻找最近公共祖先。
• 当前结点值大于q，p，就在当前结点的右子树寻找最近公共祖先。
• p，q 包含了当前结点值，即 q<=val<=p，或 q>=val>=p，那么公共祖先就是该节点。

class Solution {
  public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if (p > root->val && q > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        } else if (p < root->val && q < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        }
        return root->val;
    }
};