跳到主要内容

98. 验证二叉搜索树

题目描述​

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

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

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

示例 1：

示例1

输入：root = [2,1,3]

输出：true

示例 2：

示例2

输入：root = [5,1,4,null,null,3,6]

输出：false

解释：根节点的值是 5 ，但是其右子节点的值是 4 。

提示：

  • 树中节点数目范围在 [1, 104] 内
  • -231 <= Node.val <= 231 - 1

出处：LeetCode

解法一：递归​

思路​

递归遍历二叉树，判断每个节点是否满足二叉搜索树的定义。

实现​

function isValidBST(root: TreeNode | null): boolean {
  const dfs = (node: TreeNode | null, lower: number, upper: number): boolean => {
    if (node === null) {
      return true;
    }
    if (node.val <= lower || node.val >= upper) {
      return false;
    }
    return dfs(node.left, lower, node.val) && dfs(node.right, node.val, upper);
  };
  return dfs(root, -Infinity, Infinity);
}

复杂度分析​

  • 时间复杂度：O(n)O(n)，其中 nn 是二叉树的节点数。每个节点最多被访问一次。
  • 空间复杂度：O(n)O(n)，递归调用栈的深度最多为 nn。

解法二：中序遍历​

思路​

中序遍历二叉树，判断遍历结果是否严格递增。

实现​


function isValidBST(root: TreeNode | null): boolean {
  let prev = -Infinity;
  const stack: TreeNode[] = [];
  let node = root;
  while (node || stack.length) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop()!;
    if (node.val <= prev) {
      return false;
    }
    prev = node.val;
    node = node.right;
  }
  return true;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)，其中 nn 是二叉树的节点数。每个节点最多被访问一次。
  • 空间复杂度：O(n)O(n)，栈的空间最多为 nn。