小学生都能看懂的题解 | #判断是不是二叉搜索树#

故事背景

想象你有一排小朋友在排队，老师要求他们按照身高从小到大排队。但是，有些小朋友可能会排错位置。现在我们要检查这排小朋友是否按照身高正确地排好了队。

我们的树

我们的树就像排队的小朋友，每个节点代表一个小朋友试图按照身高（节点的值）从小到大排列。例如：

不是二叉搜索树的例子：
        1
       / \
      2   3

是二叉搜索树的例子：
        2
       / \
      1   3

判断规则

要判断一棵树是否是二叉搜索树，我们需要遵循以下规则：

1. 每个小朋友（节点）的左边的小朋友（左子树）的身高（值）都必须小于当前小朋友（节点）。
2. 每个小朋友（节点）的右边的小朋友（右子树）的身高（值）都必须大于当前小朋友（节点）。

如何实现

让我们用一个故事来说明这个过程：

1. 检查每个节点：从根节点开始，递归地检查每个节点及其左右子树。
2. 记录范围：我们需要记录每个节点允许的最小值和最大值，确保每个节点的值都在这个范围内。
3. 递归验证：对于每个节点，我们需要验证其值是否在其允许的范围内，并递归地验证其左右子树。

代码解释

让我们看看具体的代码实现：

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int x) {
        val = x;
    }
}

public class BSTValidator {
    // 判断是否为二叉搜索树的方法
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // 辅助方法，带范围检查
    private boolean isValidBST(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }

        // 检查当前节点的值是否在允许的范围内
        if (node.val <= min || node.val >= max) {
            return false;
        }

        // 递归检查左子树
        if (!isValidBST(node.left, min, node.val)) {
            return false;
        }

        // 递归检查右子树
        if (!isValidBST(node.right, node.val, max)) {
            return false;
        }

        return true;
    }
}

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。