Leetcode 验证二叉搜索树

java 实现

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, null, null);
    }
    private boolean validate(TreeNode node, Integer min, Integer max) {
        if(node == null) return true;

        if(min != null && node.val <= min) return false;
        if(max != null && node.val >= max) return false;

        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }
}

如何理解 min 和 max ？

在 验证二叉搜索树 的递归过程中，min 和 max 参数的作用是用于定义 当前节点值的有效范围。这个范围是由 父节点和祖先节点 传递下来的，并在递归过程中动态更新。

参数 min 和 max 的作用

1. min：表示当前节点值不能小于等于的下界。
2. max：表示当前节点值不能大于等于的上界。

通过递归的传参，这两个参数逐渐收窄了 当前节点的取值范围，从而确保二叉树满足 二叉搜索树 (BST) 的定义：

• 左子树 的节点值必须小于当前节点值。
• 右子树 的节点值必须大于当前节点值。

举例理解 min 和 max

给定如下二叉树：

    5
   / \
  3   7
 / \   \
2   4   8

递归过程 和 min、max 的变化如下：

1. 根节点 5：

   • 初始范围：min = null, max = null
   • 说明：根节点没有限制，任何值都有效。

2. 左子节点 3（左子树）：

   • min = null, max = 5
   • 说明：左子节点必须 小于 5（当前根节点值）。

3. 右子节点 7（右子树）：

   • min = 5, max = null
   • 说明：右子节点必须 大于 5（当前根节点值）。

4. 左子节点 3 的左子节点 2：

   • min = null, max = 3
   • 说明：2 必须小于 3。

5. 左子节点 3 的右子节点 4：

   • min = 3, max = 5
   • 说明：4 必须在 (3, 5) 范围内。

6. 右子节点 7 的右子节点 8：

   • min = 7, max = null
   • 说明：8 必须大于 7。

代码对应解析

在代码中，min 和 max 的传递体现了有效范围的逐步收窄：

private boolean validate(TreeNode node, Integer min, Integer max) {
    if (node == null) return true;

    // 检查当前节点值是否在有效范围内
    if (min != null && node.val <= min) return false; // 小于等于下界，返回 false
    if (max != null && node.val >= max) return false; // 大于等于上界，返回 false

    // 递归检查左子树和右子树，更新范围
    return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}

• validate(node.left, min, node.val)：
  • 左子树的有效范围是 min 到 node.val（上界收窄）。
• validate(node.right, node.val, max)：
  • 右子树的有效范围是 node.val 到 max（下界收窄）。

直观理解

• 在递归过程中，min 和 max 就像是两堵“墙”，夹住了当前节点的有效取值范围。
• 左子树 的节点向下传递时，右侧墙（max）会更新为父节点的值。
• 右子树 的节点向下传递时，左侧墙（min）会更新为父节点的值。

最终，通过这两堵动态更新的“墙”，可以保证整棵树的所有节点都满足二叉搜索树的定义。

总结

• min 和 max 用来动态收窄当前节点值的合法范围。
• 每次递归到左子树或右子树时，都会根据父节点值更新上下界。
• 通过这种方式，可以有效检查树中每个节点是否满足 BST 的规则。