98.验证二叉搜索树

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

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

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

前序遍历设置区间的思路or中序遍历中，利用!isValidBST(root.left) || root.val <= pre的判断条件，让每递归一次就能进行一次判断的思路

Solution：前序遍历

先遍历父节点，再遍历子节点，在遍历父节点的时候，我们需要判断其是否在一个范围里面，这个范围[lower,upper]，需要不断通过当前遍历的val进行缩小，左子树的范围是[lower,val]，而右子树的范围是[val,upper]

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
class Solution {
    // 公共接口方法，开始BST验证
    public boolean isValidBST(TreeNode root) {
        // 初始化最初的范围为最小和最大可能的值
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // 私有递归方法，用于检查每个节点是否符合BST的条件
    public boolean isValidBST(TreeNode node, long lower, long upper) {
        // 如果当前节点为空，说明此分支有效，返回true
        if (node == null) {
            return true;
        }
        // 如果节点值不在其应有的范围内，返回false
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        // 递归检查左子树，左子树的所有值必须小于当前节点值
        // 同时保持之前的下限
        if (!isValidBST(node.left, lower, node.val)) {
            return false;
        }
        // 递归检查右子树，右子树的所有值必须大于当前节点值
        // 同时保持之前的上限
        return isValidBST(node.right, node.val, upper);
    }
}

Solution：中序遍历

BST的中序遍历结果一定是递增序列，实际上我们只需要用一个变量记录节点的前一个值，比较大小即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    // 定义一个全局变量 pre，用来记录中序遍历过程中上一个访问的节点的值。
    private long pre = Long.MIN_VALUE;

    // 主方法，用于判断给定的树是否是有效的二叉搜索树。
    public boolean isValidBST(TreeNode root) {
        // 如果当前节点为空，表示这部分子树是有效的，返回 true。
        if (root == null)
            return true;

        // 先递归检查左子树。
        // 如果左子树不是有效的BST，或者当前节点的值不大于上一个节点的值（pre），则返回 false。
        if (!isValidBST(root.left) || root.val <= pre)
            return false;

        // 更新 pre 为当前节点的值，为接下来的右子树检查做准备。
        pre = root.val;

        // 递归检查右子树。
        return isValidBST(root.right);
    }
}