C++两行代码解决 | #二叉搜索树的最近公共祖先#

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

    }
};

因为本题是在二叉搜索树上找最近公共祖先，由于二叉搜索树具有左子树都小于根节点右子树都大于根节点的特性，故当找到最近公共祖先时，会出先p和q分布在根节点两侧或p和q有一点位于根节点（即(root->val - p) * (root->val - q) <= 0），此时返回当前节点值即可（不用继续向下），如果没有找到最近公共祖先（即(root->val - p) * (root->val - q) > 0），则需要根据root->val和p的大小关系选择递归左子树还是右子树（另一边不需要遍历）。

That's all

空间复杂度：O(n)，最差的情况为链表且需要找的两个节点位于末端

时间复杂度：O(n)，原因同上