方法一：前序遍历

在根节点处，判断当前值是否处于(left,right)区间内，

• 处于区间内，用root.val分别更新为左子树的右节点和右子树的左节点
• 不处于区间内则返回False

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isValidBST(self , root: TreeNode) -> bool:
        return self.check(root, float("-inf"), float("inf"))
    
    def check(self, root, left, right):
        if root is None:
            return True
        if left < root.val < right:
            return self.check(root.left, left, root.val) and self.check(root.right, root.val, right)
        else:
            return False

二、中序遍历

1. 先遍历左子树，设置pre变量
2. 比较节点值与pre变量大小（pre < root.val）
3. 变量右子树

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isValidBST(self , root: TreeNode) -> bool:
        self.pre = None
        return self.traversal(root)
    
    def traversal(self,root):
        if root is None:
            return True
        
        flag = self.traversal(root.left)
        if not flag: return False
        
        if self.pre is None:
            self.pre = root.val
            return self.traversal(root.right)
        else:
            if root.val > self.pre:
                self.pre = root.val
                return self.traversal(root.right)
            else:
                return False

三、后序遍历

1. 先遍历左子树获取左边的l_min和l_max
2. 再遍历右子树获取右边的r_min和r_max
3. 通过比较root.val和l_max和r_min的大小判断其是不是二叉搜索树

class Solution:
    def isValidBST(self , root: TreeNode) -> bool:
        _, l_max = self.traversal(root.left)
        r_min, _ = self.traversal(root.right)
        return l_max < root.val < r_min
    
    def traversal(self,root):
        if root is None:
            return float("inf"), float("-inf")

        l_min, l_max = self.traversal(root.left)
        r_min, r_max = self.traversal(root.right)
        if l_max < root.val < r_min:
            return min(l_min, root.val), max(r_max,root.val) # 因为l_min和r_max一开始是inf和-inf,所以需要用min和max
        else:
            return float("-inf"), float("inf") # 通过返回（-inf,inf），确保后面一定不是二叉搜索树