98. 验证二叉搜索树

1. 题目

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

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

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

示例 1：

img

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

示例 2：

img

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

提示：

  • 树中节点数目范围在[1, 10^4] 内
  • -2^31 <= Node.val <= 2^31 - 1

2. 思路

  • 已知题目要求通过函数验证二叉搜索树的有效性，已知二叉搜索树的特点在于中序遍历的值呈现的是单调递增的趋势
  • 利用以上特点，配合题目已知的节点值返回，在中序递归遍历的过程中，判断根部节点的值与遍历过已知的最小值进行对比
  • 如果已知最小值为null，说明当前未开始进行比对，则直接将当前节点值赋值给minVal
  • 如果当前节点值小于minVal，意味着该二叉树不是正确的二叉搜索树
  • 如果当前节点值大于minVal，则意味着该二叉树是一棵正确的二叉搜索树
  • 如果当前遍历的节点为空，则直接返回true
  • 完成左右节点递归判断后，返回leftValid && rightValid作为验证二叉搜索树的结果

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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 Integer minVal;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        var leftValid = isValidBST(root.left);

        if (minVal != null && root.val <= minVal) {
            return false;
        } 

        minVal = root.val;

        var rightValid = isValidBST(root.right);

        return leftValid && rightValid;
    }
}

4. 复杂度

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

image-20231113135223321