98 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左 子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

题解

最直接的就是先求出中序遍历，然后判断大小

var isValidBST = function (root) {
    //中序遍历
    var middleOrder = function(root, result) {
        if(!root) {
            return
        }
        middleOrder(root.left, result)
        result.push(root.val)
        middleOrder(root.right, result)
    }
    const result = []
    middleOrder(root, result)

    //判断中序是否有序
    let pre
    let final = true
    for(let i=0;i<result.length;i++) {
        if(i === 0) {
            pre = result[i]
        } else {
            if(pre >= result[i]) {
                final = false
                break
            }
            pre = result[i]
        }
    }
    return final
};

直接递归求解

先来递归无优化，剪枝的情况

var isValidBST = function (root) {
    var prev = null
    let result = true
    var isValidRecur = function (root) {
        if (!root) {
            return
        }
        isValidRecur(root.left)
        if (prev && prev.val >= root.val) {
            //如果有不合法的情况，记录下来
            result = false
        }
        prev = root;
        isValidRecur(root.right)
    }
    isValidRecur(root)
    return result
};

包含剪枝的递归求解

我们可以直接判断是否合法并且不需要递归所有节点。

var isValidBST = function (root) {
    var prev = null
    var isValidRecur = function (root) {
        if (!root) {
            return true
        }
        const left = isValidRecur(root.left)
        if (prev && prev.val >= root.val) {
            return false
        }
        prev = root;
        const right = isValidRecur(root.right)

        return left && right
    }
    return isValidRecur(root)
};

对于root = [5,1,4,null,null,3,6]，我们递归栈如下：

root = 5
进入左子树
    root = 1
    进入左子树
        root = null， 返回true
    left 为true
    prev = 1
    进入右子树
        root = null， 返回true
    right为true
    返回 left && right = true
left为true
prev = 1 && prev.val < root.val
prev = 5
进入右子树
    root = 4
    进入左子树
        root = 3
        进入左子树
            root = null，返回true
        left = true
        prev = 5 && prev.val >= root.val 返回false
    left = false
    prev = 5 && prev.val >= root.val 返回false
right = false
返回 left && right

其实还可以剪枝，当left 为false时，不用考虑right了