验证二叉搜索树（BST）是否有效【HackerRank】技术求助

嘿，我来帮你捋捋这个问题！你说输入1 2 3 4 5 6 7构建的BST明明应该有效，但代码始终返回False，这里大概率有两个常见的坑，我给你拆解下：

很多人会默认输入序列是按插入顺序构建BST，但HackerRank这类平台常用**层序遍历（广度优先）**的方式来构建树。如果是这样的话，输入1 2 3 4 5 6 7生成的树是这样的：

1
      /   \
     2     3
    / \   / \
   4  5  6  7

这棵树完全不是有效的BST！因为根节点1的左孩子是2，2比1大，直接违反了BST“左子树所有节点值小于根节点”的规则。这时候你的代码返回False其实是正确的，只是你误以为输入对应的是有效BST而已。

如果你的预期是构建一棵有效的链状BST（1→2→3→4→5→6→7，每个节点只有右孩子），那这种构建方式需要按插入顺序依次添加节点，而不是层序构建。

如果输入确实构建了有效的BST（比如刚才说的链状结构），但代码还是返回False，那大概率是你的验证逻辑只检查了当前节点和直接子节点的关系，没考虑整个子树的约束——BST要求左子树的所有节点都小于当前节点，右子树的所有节点都大于当前节点，而不仅仅是直接子节点。

给你两种正确的验证思路，你可以对照修改：

方法一：递归传递上下界（最常用的正确逻辑） #

这种方式给每个节点设定允许的取值范围，确保整个子树都符合规则：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_valid_bst(root):
    def helper(node, lower=float('-inf'), upper=float('inf')):
        # 空节点是合法的
        if not node:
            return True
        val = node.val
        # 当前节点值超出允许范围，直接无效
        if val <= lower or val >= upper:
            return False
        # 右子树的所有节点必须大于当前值，且不超过上层的上限
        if not helper(node.right, val, upper):
            return False
        # 左子树的所有节点必须小于当前值，且不低于上层的下限
        if not helper(node.left, lower, val):
            return False
        return True
    return helper(root)

方法二：中序遍历检查严格递增 #

BST的中序遍历结果一定是严格递增的，所以我们可以通过遍历收集值，再验证序列是否递增：

def is_valid_bst(root):
    prev_val = float('-inf')
    stack = []
    current_node = root

    while stack or current_node:
        # 先遍历到最左节点
        while current_node:
            stack.append(current_node)
            current_node = current_node.left
        # 弹出节点，检查是否比前一个值大
        current_node = stack.pop()
        if current_node.val <= prev_val:
            return False
        prev_val = current_node.val
        # 遍历右子树
        current_node = current_node.right
    return True

先确认HackerRank的树构建规则：如果是层序输入，那你的代码返回False是对的；如果是插入顺序构建的有效BST，那对照上面的正确逻辑修改你的验证代码就行啦。

内容的提问来源于stack exchange，提问作者Khayam Gondal