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

题目：235. 二叉搜索树的最近公共祖先

思路

不要浪费二叉搜索树的好性质；
不需要遍历整棵树；

代码

class Solution {
public:
    TreeNode* travel(TreeNode* cur, TreeNode* p, TreeNode* q)
    {   
        if(cur == NULL || cur == p || cur == q)
        {
            return cur;
        }
        // 
        if(cur->val > p->val && cur->val > q->val)
        {
            TreeNode* left = travel(cur->left, p, q);
            if(left)
            {
                return left;
            }
        }
        else if(cur->val < p->val && cur->val < q->val)
        {
            TreeNode* right = travel(cur->right, p, q);
            if(right)
            {
                return right;
            }
        }
        return cur;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return travel(root, p, q);
    }
};