98. 验证二叉搜索树

[shengxinjing]

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

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

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

输入: 2 /
1 3 输出: true 示例 2:

输入: 5 /
1 4   /
  3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。   根节点的值为 5 ，但是其右子节点值为 4 。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/validate-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[kaizige10]

// 思路：递归求子树是否是二叉搜索树
// 由于要所有子树的节点都小于或大于根节点，因此需要告诉子树根节点的值
// 所以把最大值和最小值直接传给辅助函数isSubValid
// 比较时除了和当前的root比较之外，还要和当前子树的最大最小值进行比较
var isValidBST = function(root) {
    if (!root) return true
    return isSubValid(root, -Number.MAX_VALUE, Number.MAX_VALUE)
};

/**
 * 子树是否为二叉搜索树
 * @param {*} root 子树的节点
 * @param {*} min 允许的最小值
 * @param {*} max 允许的最大值
 */
function isSubValid(root, min, max) {
    let res = true
    if (root.left) {
        // 比较当前的左子节点的值是否正确
        if (root.left.val >= root.val || root.left.val >= max || root.left.val <= min) return false
        // 递归比较左子树，左子树的最大值修改为当前根节点的值
        res = res && isSubValid(root.left, min, root.val)
    }
    if (root.right) {
        // 比较当前的右子节点的值是否正确
        if (root.right.val <= root.val || root.right.val <= min || root.right.val >= max) return false
        // 递归比较右子树，右子树的最小值修改为当前根节点的值
        res = res && isSubValid(root.right, root.val, max)
    }
    return res
}

[super-lin0]

/**
 * @param {TreeNode} root
 * @return {boolean}
 * @description 中序遍历，递归
 */
var isValidBST1 = function(root, min = -Infinity, max = Infinity) {
  if (root === null) {
    return true;
  }
  let res = true;

  if (root.left) {
    if (
      root.left.val >= root.val ||
      root.left.val >= max ||
      root.left.val <= min
    ) {
      // console.log(root.left.val <= min);

      return false;
    }
    res = res && isValidBST(root.left, min, root.val);
  }
  if (root.right) {
    if (
      root.right.val <= root.val ||
      root.right.val <= min ||
      root.right.val >= max
    ) {
      return false;
    }

    res = res && isValidBST(root.right, root.val, max);
  }

  return res;
};

var isValidBST2 = function(root, min = -Infinity, max = Infinity) {
  if (root === null) {
    return true;
  }

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

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

// 优化写法
var isValidBST3 = function(root, prev = null, next = null) {
  if (root === null) {
    return true;
  }

  if ((prev && root.val <= prev.val) || (next && root.val >= next.val)) {
    return false;
  }

  return (
    isValidBST(root.left, prev, root) && isValidBST(root.right, root, next)
  );
};

/**
 * @param {TreeNode} root
 * @return {boolean}
 * @description 中序遍历，迭代
 * 先遍历，将所有数据存放入数组中，然后针对排序好的数组进行判断
 */
var isValidBST4 = function(root) {
  let stack = [];
  let res = [];
  let current = root;

  while (current || stack.length > 0) {
    while (current) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop();
    res.push(current.val);
    current = current.right;
  }

  for (let i = 0; i < res.length - 1; i++) {
    if (res[i] >= res[i + 1]) {
      return false;
    }
  }

  return true;
};

/**
 * @param {TreeNode} root
 * @return {boolean}
 * @description 中序遍历，迭代方式
 * 利用中序遍历和二叉搜索树的特征，存入栈中的数据应该自底向上由小到大排好序了
 */
var isValidBST = function(root) {
  let stack = [];
  let current = root;
  let prevVal = "";

  while (current || stack.length > 0) {
    while (current) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop();

    if (prevVal !== "" && current.val <= prevVal) {
      return false;
    }
    prevVal = current.val;
    current = current.right;
  }
  return true;
};

[chennailiang]

var isValidBST = function (root) {
  // 中序遍历，迭代
  let result = []
  let stack = []
  let curr = root
  while (curr || stack.length > 0) {
    if (curr) {
      stack.push(curr) // 节点入栈，通过curr寻找右子树
      curr = curr.left
    } else {
      curr = stack.pop()
      result.push(curr.val)
      if(result.length > 1){
        if(result[result.length-1] <= result[result.length-2]) return false
      }
      curr = curr.right
    }
  }
  return true
};

[Hitsuki9]

// 递归
var isValidBST = function(root) {
    function helper(node, min, max) {
        if (node === null) return true;
        if (node.val >= max || node.val <= min) return false;
        return helper(node.left, min, node.val) && helper(node.right, node.val, max);
    }
    return helper(root, -Infinity, Infinity);
}

[javin9]

var isValidBST = function (root) {
  // 一个二叉搜索树的每个节点必须都满足这个条件：任意节点的值必须大于其左子树的最右节点；同时小于右子树的最左节点。
  if (!root) {
    return true
  }
  let { val } = root
  let left = rightMax(root.left)
  let right = leftMax(root.right)
  if (left && left.val >= val) {
    return false
  }
  if (right && right.val <= val) {
    return false
  }
  return isValidBST(root.left) && isValidBST(root.right)
};

function rightMax (root) {
  while (root && root.right) {
    root = root.right
  }
  return root
}

function leftMax (root) {

  while (root && root.left) {
    root = root.left
  }
  return root
}

[javin9]

var isValidBST = function (root) {
  // 一个二叉搜索树的每个节点必须都满足这个条件：任意节点的值必须大于其左子树的最右节点；同时小于右子树的最左节点。
  if (!root) {
    return true
  }
  let { val } = root
  let left = rightMax(root.left)
  let right = leftMax(root.right)
  if (left && left.val >= val) {
    return false
  }
  if (right && right.val <= val) {
    return false
  }
  return isValidBST(root.left) && isValidBST(root.right)
};

function rightMax (root) {
  while (root && root.right) {
    root = root.right
  }
  return root
}

function leftMax (root) {

  while (root && root.left) {
    root = root.left
  }
  return root
}

[javin9]

var isValidBST = function (root) {
  // 一个二叉搜索树的每个节点必须都满足这个条件：任意节点的值必须大于其左子树的最右节点；同时小于右子树的最左节点。
  if (!root) {
    return true
  }
  let { val } = root
  let left = rightMax(root.left)
  let right = leftMax(root.right)
  if (left && left.val >= val) {
    return false
  }
  if (right && right.val <= val) {
    return false
  }
  return isValidBST(root.left) && isValidBST(root.right)
};

function rightMax (root) {
  while (root && root.right) {
    root = root.right
  }
  return root
}

function leftMax (root) {

  while (root && root.left) {
    root = root.left
  }
  return root
}

[yk-knight]

var isValidBST = function(root) { let cur = root let track = [] let arr = []

while(cur || track.length > 0){
    while(cur){
        track.push(cur)
        cur = cur.left
    }
    cur = track.pop()
    if(arr.length == 0){
        arr.push(cur.val)
    }else{
        if(cur.val <= arr[arr.length-1]){
            return false
        }
        arr.push(cur.val)
    }
    cur = cur.right
}
return true

};

[yk-knight]

递归算法，先递归遍历左节点，必须小于max；再递归遍历右节点，必须大于min； var isValidBST = function(root,min=-Infinity,max=Infinity) { if(root == null) return true if(root.val <= min || root.val >= max) return false return isValidBST(root.left,min,root.val) && isValidBST(root.right,root.val,max) };