LeetCode 数据结构与算法之验证二叉搜索树

2022-04-27 148

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LeetCode 数据结构与算法之验证二叉搜索树

题目

验证二叉搜索树

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

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

节点的左子树只包含 小于 当前节点的数。

节点的右子树只包含 大于 当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

网络异常，图片无法展示

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

示例 2：

网络异常，图片无法展示

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

提示：

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

题解

解题分析

解题思路

结合题意可以知道：如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。

我们可以设计一个递归方法 isValidBST(TreeNode node, long lower, long upper) 来判断 node 参数考虑以 root 根节点为参数，判断树的所有节点值值是否都在 （lower，upper）范围内。如果 root 节点的值 val 不在 (lower, upper ) 返回内说明不满足条件直接返回，否者继续检索，直到检索完毕才说明是一个二叉搜索数。

在递归调用的过程中，我们 （lower, upper） 首次可以使用 int 的最大值，最小值。在每次调用的过程中，左子树的 upper 值为当前值 node.val , 右子树的 lower 值为当前值 node.val 。

递归方法的出口由两种情况，第一种是 node == null 返回 true , 第二种就是 node.val 是否在 lower 和 upper 区间内，如果不在返回 false.

复杂度

时间复杂度 O(N)

空间复杂度 O(N)

解题代码

题解代码如下（代码中有详细的注释说明）：

/**
 * 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 {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root , Long.MIN_VALUE, Long.MAX_VALUE);
    }
    // 递归校验方法
    public boolean isValidBST(TreeNode node, long lower, long upper) {
        // 如果为 null 表示合法
        if (node == null) {
            return true;
        }
        // 注意这里是开区间范围内合法
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        // left , right 分别判断，和设置 lower, upper 的值
        return isValidBST(node.left, lower, node.val )  && isValidBST(node.right, node.val, upper);
    }
}