验证二叉搜索树

Question

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

这是我一开始写的

// 节点的左子树只包含小于当前节点的数。
// 节点的右子树只包含大于当前节点的数。
// 所有左子树和右子树自身必须也是二叉搜索树。
var isValidBST = function(root) {
    if(root===null) return true
    if(root.left!=null&&root.left.val>=root.val)  return false
    if(root.right!=null&&root.right.val<=root.val) return false
    let isLeft = isValidBST(root.left)
    console.log(isLeft)
    let isRight = isValidBST(root.right)
    console.log(isRight)
    if(isLeft&&isRight) return true
    else    return false
};

这种情况按照我的逻辑也是对的，但不符合题目意思，并不是说左节点小于根节点，右节点大于根节点就行了，还要求左节点大于根节点的根节点

正确做法

将二叉搜索树转换为有序数组

中序遍历求出有序数组
判断数组是否有序

var isValidBST = function(root) {
    const arr = []
    digui(root,arr)
    console.log(arr)
    for (let i = 1; i < arr.length; i++) {
        // 注意要小于等于，搜索树里不能有相同元素
        if (arr[i] <= arr[i - 1]) return false;
    }
    return true
};

//中序遍历
var digui = function(root,arr) {
   if(root===null)  return
   digui(root.left,arr)
   arr.push(root.val)
   digui(root.right,arr)
};

验证二叉搜索树 ​

正确做法 ​

验证二叉搜索树

正确做法