二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

思路：

假设根节点为root,指定的两个节点分别为p,q。如果p和q分别位于root的两侧，则答案就是root。如果p,q都位于root左侧，令root=root->left,如果p,q都位于root右侧，令root=root->right。

代码：

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