【忍者算法】超市货架里的秘密：用生活常识理解二叉搜索树验证｜LeetCode 98 验证二叉搜索树网站首页 技术教程

【忍者算法】超市货架里的秘密：用生活常识理解二叉搜索树验证｜LeetCode 98 验证二叉搜索树

忍者算法_ 2025-05-14 00:01:04

简介【忍者算法】超市货架里的秘密：用生活常识理解二叉搜索树验证｜LeetCode 98 验证二叉搜索树

超市货架里的秘密：用生活常识理解二叉搜索树验证

生活小剧场：超市理货员的烦恼

假设你是超市的新员工，负责整理饮料货架。主管给你两条规则：

每层货架左边只能放低价商品，右边放高价商品
每个商品的价格标签必须清晰可见

但有个狡猾的同事把货架搞得一团糟：

    可乐 ¥5
   /     
雪碧 ¥4  芬达 ¥6 
     
    脉动 ¥5.5 ← 藏在可乐左边却比可乐便宜！

你会发现虽然直接看可乐的左右没问题，但隐藏的脉动才是问题所在。这就是验证二叉搜索树的现实写照！

问题解析：到底在验证什么？

我们需要确认这棵树满足：

每个节点左边的所有子孙（不光是直接左孩子）都比它小
每个节点右边的所有子孙（不光是直接右孩子）都比它大

就像检查整个货架区域，不能只看相邻商品，要确保整个左半区都符合规则。

常见错误：只检查眼前货物

新手最容易写成这样的错误代码：

boolean check(TreeNode node) {
    if (node == null) return true;
    if (node.left != null && node.left.val >= node.val) return false;
    if (node.right != null && node.right.val <= node.val) return false;
    return check(node.left) && check(node.right);
}

这就像只检查相邻商品：

    5
   / 
  1   6
     / 
    4   7 ← 4虽然小于6，但应该大于5！

明明4出现在5的右侧区域却比5小，这种深层问题会被漏掉。

正确方法一：传递价格标签法

核心思想

想象每个商品都带有两个隐形标签：

最低允许价格（不能比这个低）
最高允许价格（不能比这个高）

比如可乐（5元）的标签是：

左区商品：最高价 ≤5元
右区商品：最低价 ≥5元

具体步骤

给根节点设置初始范围（无限小到无限大）
检查当前节点是否在允许范围内
给左孩子设置新范围（继承父节点下限，上限设为当前值）
给右孩子设置新范围（继承父节点上限，下限设为当前值）

代码示例（Java）

public boolean isValidBST(TreeNode root) {
    return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

boolean check(TreeNode node, long minAllow, long maxAllow) {
    if (node == null) return true;
    
    // 当前商品价格是否在允许区间内
    if (node.val <= minAllow || node.val >= maxAllow) return false;
    
    // 检查左区（价格必须 < 当前价）
    boolean leftValid = check(node.left, minAllow, node.val);
    
    // 检查右区（价格必须 > 当前价）
    boolean rightValid = check(node.right, node.val, maxAllow);
    
    return leftValid && rightValid;
}

关键细节：

使用Long类型：避免数字边界问题（比如节点值是Integer.MIN_VALUE）
前开后闭区间：确保严格大于/小于

正确方法二：商品价格单检查法

核心思想

如果这是合法的BST，那么按照"左→中→右"顺序记录价格时，价格单应该是严格递增的。就像整理好的货架，从左到右价格应该一直上涨。

操作步骤

准备一个记事本记录上一个价格
按照左→中→右顺序遍历货架
每次记录新价格时，检查是否比上一个高

代码示例（Python）

def isValidBST(root):
    self.last_val = -float('inf')  # 初始设为极小值
    
    def traverse(node):
        if not node: return True
        
        # 先检查左边货架
        if not traverse(node.left): return False
        
        # 检查当前价格
        if node.val <= self.last_val:
            return False
        self.last_val = node.val  # 更新记录本
        
        # 最后检查右边货架
        return traverse(node.right)
    
    return traverse(root)