验证二叉搜索树(BST)递归代码问题：prev值始终为None的原因

代码失败的核心原因 #

你这段代码里的prev是函数内的局部变量，每次调用isValidBST（包括递归调用）时，都会重新创建一个新的prev并初始化为None。不同递归层级里的prev完全是独立的个体，修改当前层级的prev根本不会影响其他递归栈中的prev值，自然没法实现“存储前一个节点值”的需求。

具体逻辑问题拆解 #

1. 作用域隔离导致值无法传递：比如当你递归调用isValidBST(root.left)时，左子树的递归栈里会有自己的prev，哪怕左子树里把prev赋值成了某个节点值，回到当前根节点的层级时，prev还是初始的None，所以后续的prev >= root.val判断永远不会触发（因为prev一直是None）。
2. 递归返回逻辑错误：代码最后直接返回self.isValidBST(root.right)，这会导致右子树的验证结果直接作为整个函数的返回值，但实际上你需要确保左子树、当前节点、右子树全部验证通过才返回True，原代码的写法会忽略当前节点之后的验证逻辑传递。

修正方案 #

要解决这个问题，核心是让prev的值能在递归层级之间传递，常见的两种实现方式：

方式1：使用类的实例变量

把prev定义为类的实例变量，让所有递归调用共享同一个prev：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        self.prev = None  # 实例变量，所有递归调用共享
        return self._inorder_traversal(root)
    
    def _inorder_traversal(self, node):
        if not node:
            return True
        # 先验证左子树
        if not self._inorder_traversal(node.left):
            return False
        # 验证当前节点是否符合BST规则
        if self.prev is not None and self.prev >= node.val:
            return False
        # 更新prev为当前节点值
        self.prev = node.val
        # 最后验证右子树
        return self._inorder_traversal(node.right)

方式2：使用可变对象传递（比如列表）

利用Python中可变对象的引用特性，把prev放在列表里传递，递归中修改列表元素会影响外层的变量：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = [None]  # 用列表存储，可变对象可跨递归层级传递
        return self._inorder_traversal(root, prev)
    
    def _inorder_traversal(self, node, prev):
        if not node:
            return True
        if not self._inorder_traversal(node.left, prev):
            return False
        if prev[0] is not None and prev[0] >= node.val:
            return False
        prev[0] = node.val
        return self._inorder_traversal(node.right, prev)

内容的提问来源于stack exchange，提问作者ASHWIN NAIR - IMS20066