Medium

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

  • 树中节点数目范围在[1, 10^4] 内
  • -2^31 <= Node.val <= 2^31 - 1

解题思路

解题思路

验证二叉搜索树有三种主要解法：

方法一：递归范围检查（推荐）

对于每个节点，维护一个有效值的范围 [min_val, max_val]。根节点的范围是 [-∞, +∞]，对于左子树，更新上界为当前节点值；对于右子树，更新下界为当前节点值。

方法二：中序遍历

BST 的中序遍历结果必须是严格递增的序列。我们可以进行中序遍历，检查遍历过程中节点值是否严格递增。

方法三：递归返回子树范围

每次递归返回子树的最小值和最大值，然后检查是否满足 BST 性质。

方法一是最直观且效率最高的解法，时空复杂度都很优秀。方法二代码简洁，但需要额外的遍历过程。方法三相对复杂，不推荐使用。

下面的代码实现采用方法一的递归范围检查。

代码实现

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return validate(root, LLONG_MIN, LLONG_MAX);
    }
    
private:
    bool validate(TreeNode* node, long long minVal, long long maxVal) {
        if (!node) return true;
        
        if (node->val <= minVal || node->val >= maxVal) {
            return false;
        }
        
        return validate(node->left, minVal, node->val) && 
               validate(node->right, node->val, maxVal);
    }
};

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def validate(node, min_val, max_val):
            if not node:
                return True
            
            if node.val <= min_val or node.val >= max_val:
                return False
            
            return (validate(node.left, min_val, node.val) and 
                    validate(node.right, node.val, max_val))
        
        return validate(root, float('-inf'), float('inf'))

public class Solution {
    public bool IsValidBST(TreeNode root) {
        return Validate(root, long.MinValue, long.MaxValue);
    }
    
    private bool Validate(TreeNode node, long minVal, long maxVal) {
        if (node == null) return true;
        
        if (node.val <= minVal || node.val >= maxVal) {
            return false;
        }
        
        return Validate(node.left, minVal, node.val) && 
               Validate(node.right, node.val, maxVal);
    }
}

var isValidBST = function(root) {
    function validate(node, minVal, maxVal) {
        if (!node) return true;
        
        if (node.val <= minVal || node.val >= maxVal) {
            return false;
        }
        
        return validate(node.left, minVal, node.val) && 
               validate(node.right, node.val, maxVal);
    }
    
    return validate(root, -Infinity, Infinity);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)需要访问每个节点一次，n为节点数
空间复杂度O(h)递归调用栈的深度，h为树的高度，最坏情况为O(n)

相关题目