98. 验证二叉搜索树 🟨

题目

98. 验证二叉搜索树 中等

题目

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

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

示例 1：
输入：root = [2,1,3]
输出：true

示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

陷阱

二叉搜索树（左节点 < 根节点 < 右节点），提笔就写出这样的错误逻辑：

// ❌ 典型的错误想法
if (node.left && node.left.val >= node.val) return false;
if (node.right && node.right.val <= node.val) return false;

// 为什么错？ 请看下面这棵树：
      5
     / \
    4   6
       / \
      3   7

所以，验证 BST 的核心不仅是比较左右孩子，而是上下界限（Bounds） 的约束。

题解

方法：深度优先 DFS

解题思路

每一个节点在被访问时，不仅要知道自己是谁，还要知道自己允许的取值范围（min, max）。

根节点：无拘无束，范围是 (-Infinity, Infinity)。
向左走：最大值被限制住了。左孩子的值必须严格小于当前节点的值。
向右走：最小值被限制住了。右孩子的值必须严格大于当前节点的值。

只要在往下走的过程中，有任何一个节点的值越界了，整棵树就是非法的。

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function isValidBST(root) {
  const validate = (node, min, max) => {
    console.log('♻️ node', node ? node.val : null, 'min', min, 'max', max)

    // 空节点默认是合法的 BST
    if (node === null) return true

    // 如果当前节点的值越界了，直接判死刑
    // 注意：BST 中不能有相等的值，所以是 <= 和 >=
    if (node.val <= min || node.val >= max) {
      return false
    }

    // 递归检查左子树，最大界限更新为当前节点的值
    const isLeftValid = validate(node.left, min, node.val)
    // 递归检查右子树，最小界限更新为当前节点的值
    const isRightValid = validate(node.right, node.val, max)

    return isLeftValid && isRightValid
  }

  return validate(root, -Infinity, Infinity)
}

const tree = new TreeNode(4)
tree.left = new TreeNode(2, new TreeNode(1), new TreeNode(3))
tree.right = new TreeNode(5, null, new TreeNode(6))
console.log('🌰', JSON.stringify(isValidBST(tree)))

console.log('------')

const tree2 = new TreeNode(5)
tree2.left = new TreeNode(1)
tree2.right = new TreeNode(4, new TreeNode(3), new TreeNode(6))
console.log('🌰', JSON.stringify(isValidBST(tree2)))

执行结果

♻️ node 4 min -Infinity max Infinity
♻️ node 2 min -Infinity max 4
♻️ node 1 min -Infinity max 2
♻️ node null min -Infinity max 1
♻️ node null min 1 max 2
♻️ node 3 min 2 max 4
♻️ node null min 2 max 3
♻️ node null min 3 max 4
♻️ node 5 min 4 max Infinity
♻️ node null min 4 max 5
♻️ node 6 min 5 max Infinity
♻️ node null min 5 max 6
♻️ node null min 6 max Infinity
🌰 true
------
♻️ node 5 min -Infinity max Infinity
♻️ node 1 min -Infinity max 5
♻️ node null min -Infinity max 1
♻️ node null min 1 max 5
♻️ node 4 min 5 max Infinity
🌰 false

方法：中序遍历

时间复杂度：O(n)
空间复杂度：O(n)

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function isValidBST(root) {
  let stack = []
  let inorder = -Infinity

  while (stack.length || root !== null) {
    console.log(
      '♻️ stack',
      stack.map(node => node.val),
      'inorder',
      inorder,
    )

    while (root !== null) {
      stack.push(root)
      root = root.left
    }

    console.log(
      'stack',
      stack.map(node => node.val),
    )

    root = stack.pop()
    // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
    if (root.val <= inorder) {
      console.log('❌', root.val, inorder)
      return false
    }
    inorder = root.val
    root = root.right
  }
  return true
}

const tree = new TreeNode(4)
tree.left = new TreeNode(2, new TreeNode(1), new TreeNode(3))
tree.right = new TreeNode(5, null, new TreeNode(6))
console.log('🌰', JSON.stringify(isValidBST(tree)))

console.log('------')

const tree2 = new TreeNode(5)
tree2.left = new TreeNode(1)
tree2.right = new TreeNode(4, new TreeNode(3), new TreeNode(6))
console.log('🌰', JSON.stringify(isValidBST(tree2)))

执行结果

♻️ stack [] inorder -Infinity
stack [ 4, 2, 1 ]
♻️ stack [ 4, 2 ] inorder 1
stack [ 4, 2 ]
♻️ stack [ 4 ] inorder 2
stack [ 4, 3 ]
♻️ stack [ 4 ] inorder 3
stack [ 4 ]
♻️ stack [] inorder 4
stack [ 5 ]
♻️ stack [] inorder 5
stack [ 6 ]
🌰 true
------
♻️ stack [] inorder -Infinity
stack [ 5, 1 ]
♻️ stack [ 5 ] inorder 1
stack [ 5 ]
♻️ stack [] inorder 5
stack [ 4, 3 ]
❌ 3 5
🌰 false

本页目录