2020-06-20 二叉树验证 98. Validate Bi

https://leetcode.com/problems/validate-binary-search-tree/submissions/

My answer / AC

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    let dfs = function(node, min=-Number.MAX_SAFE_INTEGER, max=Number.MAX_SAFE_INTEGER) {
        let isValid = true;
        if(!node) return isValid;


        if(node.val<=min || node.val>=max){
            isValid=false;
        }

        
        return isValid && dfs(node.left, min, node.val) && dfs(node.right, node.val, max);
    }
    return dfs(root);
};

抄答案的，还调了半天.
遍历是基本没问题的，但是要获得当前node能取的值的取值范围（最大/最小值），否则容易出现子树中存在比父节点更大的值

Best answer

const isValidBST = (root, a=-Infinity, b=Infinity) => {
    return  !root ||
            a < root.val && root.val < b &&
            isValidBST(root.left, a, root.val) && 
            isValidBST(root.right, root.val, b);
}

Recap

要反复练练手。