98-验证二叉搜索树

Doublew2w大约 3 分钟

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

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

节点的左
子树

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

示例 1：

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

示例 2：

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

提示：

树中节点数目范围在 [1, 10 ⁴] 内
-2 ³¹ <= Node.val <= 2 ³¹ - 1

思路：中序遍历+双指针

遇到二叉搜索树，使用中序遍历，即「左中右」的遍历顺序

定义一个最小值 prev 当成是当前节点遍历的上一个节点值，目的是用来判断是否符合二叉搜索树的定义

递归终止条件：

如果树为空，直接返回 true。（空树符合二叉搜索树的定义）
如果当前节点的 val <= prev 即 root.val <= prev, 说明左子树是不符合二叉搜索树，直接返回 false
如果提前发现左子树不符合二叉搜索树的定义，也提前返回 false

在「中节点」处理的时候，将 prev 更新为当前节点的值。如果是第一次比较的情况，比较的节点也是符合保证 > prev的

然后再遍历右子树。

关键点

定义一个前节点来做判断，并且要做好更新的

代码1


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
// 简洁实现·中序遍历
class Solution {
    private long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }
        if (root.val <= prev) { // 不满足二叉搜索树条件
            return false;
        }
        prev = root.val;
        return isValidBST(root.right);
    }
}

复杂度分析

令 n 为二叉树的节点个数。

时间复杂度： $O(n)$ ，在递归调用的时候二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。
空间复杂度： $O(n)$ ，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。

代码2

class Solution {
    private boolean isValidBSTUtil(TreeNode node, long min, long max) {
        if (node == null) return true; // 正确的递归终止条件

        // 检查当前节点的值是否在允许的范围内
        if (node.val <= min || node.val >= max) return false;

        // 递归地检查左子树和右子树，同时更新限制条件
        return isValidBSTUtil(node.left, min, node.val) && 
               isValidBSTUtil(node.right, node.val, max);
    }

    public boolean isValidBST(TreeNode root) {
        // 从最小值Long.MIN_VALUE到最大值Long.MAX_VALUE开始递归
        return isValidBSTUtil(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
}

98-验证二叉搜索树

题目地址(98. 验证二叉搜索树 - 力扣（LeetCode）)

题目描述

思路：中序遍历+双指针

关键点

代码1

代码2