leetcode 98. Validate Binary Search Tree(验证二叉搜索树)

题目要求

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解题思路

（1）递归
凭直觉看这是一个平凡的问题。只需要遍历整棵树，检查 node.right.val > node.val 和 node.left.val < node.val 对每个结点是否成立。
问题是，这种方法并不总是正确。不仅右子结点要大于该节点，整个右子树的元素都应该大于该节点。例如:

如上图所示，我们在节点5的时候发现，他的左右孩子节点都符合要求，但是在右孩子的子节点有一个4中却不符合BST定义。
这意味着我们需要在遍历树的同时保留结点的上界与下界，不仅要比较时不仅比较子结点的值，也要与上下界比较。
（2）中序遍历
BST的一条关键的性质就是：通过中序遍历可以得到一个有序的结果，那这意味着什么？意味着如果你通过中序遍历得到的是一个无序的结果，或者说不满足递增的顺序那么该树就不是BST。我们借助一个list来实现存放数据，用一个变量Pre来存放当前结点的前一个值用于规则的比较。

主要代码python

递归法

# 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 isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def helper(node, lower=float('-inf'), upper=float('inf')): # 初始上下界
            if not node:
                return True
            
            val = node.val
            if val<= lower or val >= upper: # 符合规则：当前结点在下界和上界之间
                return False
            if not helper(node.left, lower, val): # 验证左子树
                return False
            if not helper(node.right, val, upper):# 验证右子树
                return False
            return True
        
        return helper(root)
        
        

时间复杂度 : O(N)。每个结点访问一次。
空间复杂度 : O(N)。我们跟进了整棵树。
中序遍历法

# 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 isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        stack, inorder = [], float('-inf')
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop() #中序出栈
                if root.val <= inorder:
                    return False
                inorder = root.val
                root = root.right
        return True # root为空的话也可以直接返回
        

时间复杂度 : 最坏情况下（树为二叉搜索树或破坏条件的元素是最右叶结点）为O(N)。
空间复杂度 : O(N) 用于存储 stack

原题链接：https://leetcode-cn.com/problems/validate-binary-search-tree