题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

我的解法——记录当前上下界+比较（AC）

记录子树的上界和下界，root的左子树一定小于root的值，root的右子树一定大于root的值，然后递归左子树和右子树。每个结点都得和两个数比，它必须在这两个数的范围之内，其中一个就是它的父节点，另外一个是它的某个祖先借点
float(‘inf’)在py中代表无穷大
这个题蛋疼的是边界条件判定！！！先把边界case列出来！
时间时间复杂度均为O(n)，空间复杂度为O(1)。
Beat59%

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

class Solution(object):
    def myisValidBST(self,root,minnow,maxnow):
        flag1 = False
        flag2 = False
        
        if(root.val < maxnow):
            if(root.left != None and self.myisValidBST(root.left,minnow,min(maxnow,root.val))):  # 注意缩小边界区间
                flag1 = True
            elif(root.left == None):
                flag1 = True

        if(root.val > minnow):
            if(root.right != None and self.myisValidBST(root.right,max(minnow,root.val),maxnow)):
                flag2 = True
            elif(root.right == None):
                flag2 = True
            
        return (flag1 and flag2)
    
    
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        
        if(root == None):
            return True
        else:
            return self.myisValidBST(root,-float('inf'),float('inf'))
        
        

最优解法——中序遍历是否有序

二叉查找树中序遍历转化成数组可以得到一个递增的序列，我们只需中序遍历二叉树，判断其序列是否递增即可。
中序遍历只遍历二叉树一次，算法时间复杂度O（n），空间复杂度O（c）