2种方式验证二叉搜索树

在这里插入图片描述

解法1：中序遍历 + 单调性检查

二叉搜索树有一个重要性质：中序遍历的结果必然是严格递增的序列。

利用这个性质，在中序遍历过程中，用一个 pre 指针记录前一个访问的节点，每次访问新节点时检查是否满足 pre.val < cur.val。

代码实现

 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


public static int MAXN = 10001;
public static TreeNode[] stack = new TreeNode[MAXN];
public static int r;

public static boolean isValidBST(TreeNode head) {
    if (head == null) {
        return true;
    }
    TreeNode pre = null;
    r = 0;
    
    // 手写栈实现中序遍历
    while (r > 0 || head != null) {
        if (head != null) {
            // 左子树未处理完，继续向左并入栈
            stack[r++] = head;
            head = head.left;
        } else {
            // 左子树已处理完，弹出当前节点
            head = stack[--r];
            
            // 检查单调性：前一个节点的值必须小于当前节点
            if (pre != null && pre.val >= head.val) {
                return false;
            }
            
            pre = head;
            head = head.right;
        }
    }
    return true;
}

解法2：递归 + 区间验证

对于BST，不仅要比较父子节点，还要保证整棵子树的值范围合法。

因此，需要在递归过程中收集每棵子树的最小值和最大值。

代码实现

 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


public static long min, max;

public static boolean isValidBST(TreeNode head) {
    if (head == null) {
        min = Long.MAX_VALUE;
        max = Long.MIN_VALUE;
        return true;
    }
    
    // 递归处理左子树
    boolean lok = isValidBST(head.left);
    long lmin = min;
    long lmax = max;
    
    // 递归处理右子树
    boolean rok = isValidBST(head.right);
    long rmin = min;
    long rmax = max;
    
    // 更新当前子树的最小值和最大值
    min = Math.min(Math.min(lmin, rmin), head.val);
    max = Math.max(Math.max(lmax, rmax), head.val);
    
    // 验证BST性质：
    // 1. 左右子树各自是BST
    // 2. 左子树最大值 < 当前节点 < 右子树最小值
    return lok && rok && lmax < head.val && head.val < rmin;
}

如果觉得有帮助，欢迎点赞、关注、转发~