前序、中序和后序遍历

验证二叉搜索树

前序

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def f(node:Optional[TreeNode],l,r):
            if node is None:
                return True
            return node.val>l and node.val<r and f(node.left,l,node.val) and f(node.right,node.val,r)
        a=-inf
        b=inf
        return f(root,a,b)

中序

class Solution:
    pre = -inf
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        if not self.isValidBST(root.left) or root.val <= self.pre:
            return False
        self.pre = root.val
        return self.isValidBST(root.right)

后序

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node: Optional[TreeNode]) -> Tuple:
            if node is None:
                return inf, -inf
            l_min, l_max = dfs(node.left)
            r_min, r_max = dfs(node.right)
            x = node.val
            # 也可以在递归完左子树之后立刻判断，如果不是二叉搜索树，就不用递归右子树了
            if x <= l_max or x >= r_min:
                return -inf, inf
            return min(l_min, x), max(r_max, x)
        return dfs(root)[1] != inf