迭代法验证二叉搜索树：代码失效原因及可行性探讨

一、能不能用迭代法验证BST？ #

当然可以，迭代法完全能实现BST的验证，常见有两种靠谱思路：

• 利用BST中序遍历结果严格递增的特性，遍历过程中记录前一个节点的值，实时对比当前节点是否大于前一个节点；
• 用栈模拟递归逻辑，跟踪每个节点的合法取值范围（每个节点必须大于左边界、小于右边界）。

二、你的代码存在的问题 #

1. 语法错误 #

函数定义行末尾缺了冒号：def is_bst(node):，这会直接导致代码无法运行。

2. 核心逻辑错误：只检查直接子节点，忽略整棵子树的范围限制 #

BST的规则不是只看当前节点和直接左右子节点的大小，而是左子树所有节点都要小于当前节点，右子树所有节点都要大于当前节点。举个反例：

5
   / \
  3   7
     /
    2

你的代码会检查5>3、5<7、7>2，认为所有直接子节点都符合要求，错误返回True，但实际上2作为右子树的节点，却小于根节点5，这完全违反BST规则。你的代码根本没检查这类跨层级的范围问题。

3. 队列操作的逻辑错误 #

处理右节点时，你先判断if node.right并append一次，之后又不管node.right是否存在，再次执行q.append(node.right)：

• 如果node.right存在，会被重复加入队列两次，造成重复处理；
• 如果node.right不存在，会把None加入队列，属于无效操作，浪费资源。

三、正确的迭代实现示例 #

思路1：中序遍历验证递增 #

def is_bst(node):
    stack = []
    prev = None
    current = node
    while stack or current:
        # 先遍历到当前分支的最左节点
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        # 检查当前节点是否大于前一个节点（保证递增）
        if prev is not None and current.data <= prev.data:
            return False
        prev = current
        # 切换到右子树
        current = current.right
    return True

思路2：跟踪节点的合法取值范围 #

def is_bst(node):
    if not node:
        return True
    # 栈中存储(当前节点, 左边界, 右边界)
    stack = [(node, float('-inf'), float('inf'))]
    while stack:
        current, lower, upper = stack.pop()
        # 当前节点超出合法范围则直接返回False
        if current.data <= lower or current.data >= upper:
            return False
        # 左子树的右边界是当前节点值，左边界不变
        if current.left:
            stack.append((current.left, lower, current.data))
        # 右子树的左边界是当前节点值，右边界不变
        if current.right:
            stack.append((current.right, current.data, upper))
    return True

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