验证二叉搜索树

约 801 字大约 3 分钟

二叉树中等百度

2024-12-07

🌳 题目描述：

判断一棵二叉树是不是有效的二叉搜索树

二叉搜索树：

节点的值都大于其左子树所有节点的值
节点的值都小于其右子树所有节点的值
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [10, 8, 15, 1, 9, 13, 17]

输出：true

解释图例：

示例 2：

输入：root = [10, 8, 9]

输出：false

解释图例：

🕵🏽 面试评估：

这道题考察候选人对二叉搜索树（BST）性质的理解，并且要求候选人能够使用递归或迭代方法（如中序遍历）来检查二叉树是否符合二叉搜索树的规则，并通过适当的边界值（例如，子树值的上下限）来验证每个节点是否符合二叉搜索树的要求

📝思路分析：

这道题我们采用递归的写法，每次递归来检查每个节点是否满足 BST 即二叉搜索树的条件。

二叉搜索树相对应的性质是：

节点的值都大于其左子树所有节点的值
节点的值都小于其右子树所有节点的值
所有左子树和右子树自身必须也是二叉搜索树。

以案例一为例，解析如下。

在递归过程中，对于左子树节点，它们的值必须小于当前节点的值，说明它的值只能是在 lower 和当前节点的值之间，而右子树节点，它们的值必须大于当前节点的值，说明它的值只能是在当前节点的值和 upper 之间，通过每一次递归更新 lower 和 upper 的值，如果当前的值小于等于 lower 或者大于等于 upper，则说明当前的节点不满足 BST 条件，返回 false，随后递归检查左子树和右子树。

递归的终止条件是，当我们遍历到一个空节点时，返回 true，因为空树不影响判断结果，可以被视为二叉搜索树。

💻代码：

Java

    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean isValidBSTHelper(TreeNode root, long lower, long upper) {
        if (root == null) {
            return true;
        }
        
        if (root.val <= lower || root.val >= upper) {
            return false;
        }
        
        return isValidBSTHelper(root.left, lower, root.val) && isValidBSTHelper(root.right, root.val, upper);
    }

Python

    def isValidBST(self, root):
        return self.isValidBSTHelper(root, float('-inf'), float('inf'))
    
    def isValidBSTHelper(self, root, lower, upper):
        if root is None:
            return True
        if root.val <= lower or root.val >= upper:
            return False
        return self.isValidBSTHelper(root.left, lower, root.val) and self.isValidBSTHelper(root.right, root.val, upper)