98. 验证二叉搜索树
2025-03-25 10:14:57 #LeetCode

Problem: 98. 验证二叉搜索树

思路

最近做二叉树的题目比较多，这里面涉及到的主要是各种各样的递归问题。以这题为例复习和总结一下二叉树的递归问题。

本题的目标是验证二叉树是否为二叉搜索树。

方法一

朴素来看，要验证是二叉搜索树，我们需要保证左子树、右子树都是二叉搜索树，以及当前节点的值大于左子树的最大值，小于右子树的最小值。

这样，我们定义一个函数，其返回值是当前子树的最小值和最大值，用作比较目的。我们定义空子树的最小值为正无穷大，最大值为负无穷大，这样一定能够使得其父节点满足二叉搜索树性质，而且也为二叉搜索树。

然后，对于非空子树，我们先判断其是否满足二叉搜索树性质，如果不满足，则问题的答案就是false。如果满足，我们把更新当前子树的最大最小值。最小值设为左子树的最小值（和当前节点值对比，防止左节点为空），最大值设为右子树的最大值（同理对比当前节点）。

当递归完成时，我们就可以找到是否有子树不满足二叉搜索树性质，若全部满足则为二叉搜索树。

方法二

可以看到，前一个方法需要经常创建最大最小值对，造成了一定的空间开销。

注意到二叉搜索树还有一个性质，也就是其中序遍历是单调序列。

如果我们利用二叉搜索树的性质，把函数的返回值设为当前子树是否为二叉搜索树，并记录前一个节点的值，通过中序遍历，我们就能判断是否为二叉搜索树。

具体过程见代码。

递归

递归的题目我认为本质是这样的：
递归终止条件时是正确的，然后前一层在假设子问题正确后运用算法能保持正确性。类似于数学归纳法。

换一种说法就是：

  1. 递归终止条件的正确性：当问题规模缩小到最简单的情况时，递归能够直接给出正确的结果。
  2. 递归关系的正确性：假设对更小规模的子问题的求解是正确的，通过递归关系能够正确地求解原问题。

递归问题除了关注终止条件、子问题和当前问题的关系以外，我认为还需要关注递归函数返回了什么，参数是什么，维持了什么性质。从这些切入点入手，递归问题就更容易思考。

递归时的数据传递可以用返回值，参数或者全局变量。我认为能够利用递归性质时最好使用返回值。难以观察递归性质时可以用全局变量，但是全局变量会影响可读性和可维护性。参数更适合作为对函数外无影响的条件。

Code

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
/**
 * 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 {
    boolean ans = true;
    public boolean isValidBST(TreeNode root) {
        dfs(root);
        return ans;
    }
    //返回：当前子树的最小、最大值
    public long[] dfs(TreeNode node) {
        if (node == null) return new long[]{Long.MAX_VALUE, -Long.MAX_VALUE};
        long[] left = dfs(node.left);
        if (left[1] >= node.val) ans = false;
        long[] right = dfs(node.right); 
        if (right[0] <= node.val) ans = false;
        right[0] = Math.min(left[0], node.val);
        right[1] = Math.max(right[1], node.val);
        return right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
	//中序遍历过程的前一个值，实际上就是小于当前值的第一个值。
    long pre = -Long.MAX_VALUE;
    //能够判断该子树是否为二叉搜索树，最后pre为最右下节点的值（如果为二叉搜索树，则为该子树最大值）
    public boolean isValidBST(TreeNode root) {
		//递归返回情况
        if (root == null) return true;
        // 保证左子树为二叉搜索树
        if (!isValidBST(root.left)) return false;
        // 保证左子树小
        if (root.val <= pre) return false;
        pre = root.val;
        // 第一次比较值时，节点为右子树的最左下节点，会比较是否比当前节点值大
        // 保证右子树为二叉搜索树
        if (!isValidBST(root.right)) return false;
        return true;
    }
}

上一页
2025-03-25 10:14:57 #LeetCode