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

说实话，写了这么些关于树的题目，感觉树的题目就应该用递归写，只要思路想清晰，写起来真舒服。

这题仔细分析一下就会发现，关键点在于，p和q一定在最近祖先的两侧或本身就是最近祖先。所以就可以自顶向下去找，如果都落在一侧，那这个结点肯定不是最近的祖先，一旦发现落在两侧（包括落在子树的根上），那这个结点就是最近的共同祖先。

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