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

根据二叉搜索树的特性优化

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // 保证 p < q
        if (p > q) swap(p, q);
        // 如果 p 小于等于当前节点的值 root->val 且当前节点的值 root->val 大于等于 q，那么 root 就是最近公共祖先
        // 包含 p < root->val && root->val == q
        // p == root->val && root->val < q
        // p < root->val && root->val < q
        // 没有两个都相等的情况，因为 p 和 q 不是相同节点
        if (p <= root->val && root->val <= q) return root->val;
        // 否则如果当前节点的值大于 p 和 q，那么答案一定在左子树中
        if (root->val > p && root->val > q) return lowestCommonAncestor(root->left, p, q);
        // 否则在右子树中
        return lowestCommonAncestor(root->right, p, q);
    }
};