python多种算法对比图解实现 验证二叉树搜索树【力扣98】

输入: root = [2,1,3]
输出: True
解释: 给定二叉树是以下结构，显然是 BST:
    2
   / \
  1   3

输入: root = [5,1,4,null,null,3,6]
输出: False
解释: 根节点的右子树包含比根节点小的值 (3 < 5)。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def isValidBST(root):
    """
    利用中序遍历验证二叉搜索树
    :param root: TreeNode, 二叉树的根节点
    :return: bool, 是否为有效的二叉搜索树
    """
    prev = None
    
    def inorder(node):
        nonlocal prev
        if not node:
            return True
        if not inorder(node.left):
            return False
        if prev is not None and node.val <= prev:
            return False
        prev = node.val
        return inorder(node.right)
    
    return inorder(root)

2
   / \
  1   3

步骤1: 访问根节点 2
步骤2: 移至左子节点 1
步骤3: 打印左子节点 1，回到根节点 2
步骤4: 打印根节点 2，移至右子节点 3
步骤5: 打印右子节点 3

2           <- 根节点开始
   / \
  1   3         <- 先访问左子树，然后根节点，最后右子树

中序遍历步骤：
1. 访问节点 2 的左子树（节点 1）
2. 访问节点 1，没有左子树，打印 1，记录 prev = 1
3. 返回到节点 2，prev = 1，当前节点 = 2，2 > 1 成立，打印 2，记录 prev = 2
4. 访问节点 2 的右子树（节点 3）
5. 访问节点 3，没有左子树，打印 3，记录 prev = 3

1 -> 2 -> 3     <- 中序遍历结果应该形成递增序列

def isValidBST(root):
    def validate(node, low=float('-inf'), high=float('inf')):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return validate(node.left, low, node.val) and validate(node.right, node.val, high)
    
    return validate(root)

def isValidBST(root):
    stack, prev = [], float('-inf')
    
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if root.val <= prev:
            return False
        prev = root.val
        root = root.right
    
    return True