98. Validate Binary Search Tree

原题：98. Validate Binary Search Tree

解法一

时间复杂度：O(n)

// Runtime: 64 ms, faster than 73.11% of JavaScript online submissions for Validate Binary Search Tree.
// Memory Usage: 37.3 MB, less than 84.62% of JavaScript online submissions for Validate Binary Search Tree.
var isValidBST = function(root, min=-Infinity, max=Infinity) {
    if(!root) {
        return true;
    }

    if(root.val<=min || root.val>=max) {
        return false;
    }

    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
};

解法二

时间复杂度：O(n)

// Runtime: 68 ms, faster than 50.77% of JavaScript online submissions for Validate Binary Search Tree.
// Memory Usage: 37.1 MB, less than 100.00% of JavaScript online submissions for Validate Binary Search Tree.

//利用二叉搜索树先序遍历是升序的这个特性
var isValidBST = function(root) {
    let prev = -Infinity;
    const helper = function(node) {
        if(!node) {
            return true;
        }
        
        if(!helper(node.left)) {
            return false;
        }

        if(prev>=node.val) {
            return false;
        }
        prev = node.val;

        return helper(node.right);
    };

    return helper(root);
};

Test Cases

test("test1", ()=>{
    expect(isValidBST(makeTree([2,1,3]))).toEqual(true);
})

test("test2", ()=>{
    expect(isValidBST(makeTree([5,1,4,null,null,3,6]))).toEqual(false);
})

test("test3", ()=>{
    expect(isValidBST(makeTree([]))).toEqual(true);
})

test("test4", ()=>{
    expect(isValidBST(makeTree([1]))).toEqual(true);
})

test("test5", ()=>{
    expect(isValidBST(makeTree([1, 1]))).toEqual(false);
})

test("test6", ()=>{
    expect(isValidBST(makeTree([10,5,15,null,null,6,20]))).toEqual(false);
})