题解 | #判断是不是二叉搜索树#

看了题解我的方法最麻烦了，先说下题解的好方法：

1. 中序遍历，序列升序则是二叉搜索树；

2.递归法，遍历第一个节点，判断该结点是否在指定范围内，然后遍历该结点的左右子节点，遍历左结点时，范围是父节点范围的左边界和父节点值作为有边界，依次类推。

3.我实现的方法：递归法，判断左右子树是不是二叉搜索树，如果不是，直接返回false，都是的话取出左子树最大值和右子树最小值，看左子树最大值是不是比父节点小，右子树最小值是不是比父节点大。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    def isValidBST(self , root: TreeNode) -> bool:
        # write code here
        if root == None:
            return True
        else:
            tag1 = self.isValidBST(root.left)
            tag2 = self.isValidBST(root.right)
            if tag1 and tag2:
                left_max = self.getmax(root.left)
                right_min = self.getmin(root.right)
                if root.val > left_max and root.val < right_min:
                    return True
                else:
                    return False
            else:
                return False

    def getmax(self , root):
        if root==None:
            return -2 ** 31
        else:
            tmp = root
            while tmp.right:
                tmp = tmp.right
            return tmp.val
    def getmin(self , root):
        if root==None:
            return 2 ** 31
        else:
            tmp = root
            while tmp.left:
                tmp = tmp.left
            return tmp.val


root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
print(Solution().isValidBST(root))