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

思路

因为二叉搜索树是有序的，所以和上一题还是不一样
1.确定终止条件
遇到空返回
2.确定单层递归的逻辑
在遍历二叉搜索树的时候就是寻找区间[p->val, q->val]（注意这里是左闭又闭）那么如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历（说明目标区间在左子树上）。

JS语言

var lowestCommonAncestor = function(root, p, q) {
    const travle = function(root, p,q){
        if(!root){         //中
            return root;
        }
        if(root.val>p.val && root.val>q.val){ //左
            let left = travle(root.left,p,q)
            if(left){
                return left;
            }
        }
        if(root.val < p.val && root.val <q.val){ //右
            let right = travle(root.right,p,q)
            if(right){
                return right;
            }
        }
        return root;
    }
    return travle(root,p,q);
};