迭代法验证二叉搜索树（BST）的代码错误排查求助

问题背景 #

给定二叉树根节点，判断其是否为有效的二叉搜索树（BST）。有效BST需满足：

• 节点左子树的所有节点值小于该节点值；
• 节点右子树的所有节点值大于该节点值；
• 左右子树本身也必须是有效BST。

待分析的迭代实现代码 #

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        
        level=[root]
        
        while level:
            for k in level:
                
                if k.left:
                    if k.left >= k.val:
                        return False
                    
                if k.right:
                    if k.right <= k.val:
                        return False
                    
            level=[leaf for n in level for leaf in (n.left,n.right) if leaf]
                    
        return True

代码问题分析 #

该代码在测试用例[2,1,3]时无法正常工作，问题出在这段代码：

if k.left:
   if k.left >= k.val:
      return False

这段代码存在两个核心错误：

1. 对象与数值的错误比较：k.left是TreeNode类型的对象，直接和k.val（数值类型）进行比较是逻辑错误。Python中对象和数值直接比较不会正确判断节点值的大小，甚至可能触发类型错误，正确的比较应该是k.left.val >= k.val，即取左子节点的val属性来和当前节点值对比。
2. 未满足BST的完整约束：这段代码仅检查了当前节点与直接左子节点的大小关系，但BST要求左子树的所有节点值都小于当前节点值，而非仅仅直接子节点。比如若左子树的右子节点值大于当前节点，这段代码无法检测到该违规情况，本质上是没有为每个节点设置合法值的上下边界范围。

修正思路示例 #

要正确验证BST，需要为每个节点维护允许的数值范围（下界和上界），迭代遍历过程中检查节点值是否在合法范围内：

class Solution(object):
    def isValidBST(self, root):
        if not root:
            return True
        # 栈中保存(节点, 下界, 上界)
        stack = [(root, float('-inf'), float('inf'))]
        while stack:
            node, low, high = stack.pop()
            if node.val <= low or node.val >= high:
                return False
            if node.left:
                stack.append((node.left, low, node.val))
            if node.right:
                stack.append((node.right, node.val, high))
        return True

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