给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
 2
  / \
 1  3
输出: true
示例 2:
输入:
 5
  / \
 1  4
  / \
 3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。

解法 1

利用递归进行中序遍历，中序遍历后二叉搜索树所有节点由小到大排列，所以判断中序遍历结果是否和中序遍历结果去重并排序的结果相等。

def is_valid_bst(root):
    inorder = helper(root)
    return inorder == list(sorted(set(inorder)))

def helper(root):
    if not root:
        return []
    return in_order(root.left) + [root.val] + in_order(root.right)

执行用时 :64 ms
内存消耗 :17.5 MB

时间复杂度：中序遍历的时间复杂度为 O(n)，快排的时间复杂度为 O(n log n)，所以时间复杂度为 O(n log n)
空间复杂度：这里用列表存储中序遍历及快排的结果，所以空间复杂度为 O(n)

解法 2

利用递归进行中序遍历，中序遍历后二叉搜索树所有节点由小到大排列，所以在中序遍历过程中，可以判断前置节点是否小于当前节点，若不符合则不是二叉搜索树。

class Solution:
    def is_valid_bst(self, root):
        self.prev = None
        return self.helper(root)

    def helper(self, root):
        if not root: # 空节点返回True
            return True
        if not self.helper(root.left): # 遍历左子树
            return False
        if self.prev and self.prev.val >= root.val: # 若前置节点大于或等于当前节点，则不是二叉搜索树，返回False
            return False
        self.prev = root # 将当前节点设为前置节点
        return self.helper(root.right) # 遍历右子树

执行用时 :60 ms
内存消耗 :16.6 MB

时间复杂度：最坏的情况是遍历所有节点，所以时间复杂度为 O(n)
空间复杂度：空间大小取决于输入二叉树的节点个数 n，所以空间复杂度为 O(n)

解法 3

利用递归进行中序遍历，在二叉搜索树中，节点的左子树只包含小于当前节点的数，节点的右子树只包含大于当前节点的数，所以在遍历过程中，可以将当前节点设为左子树的最大值、右子树的最小值，从而判断当前节点是否比所有左子树节点大，比所有右子树节点小。

def is_valid_bst(root):
    return helper(root, None, None)


def helper(root, min, max):
    if not root:
        return True
    if min is not None and root.val <= min:
        return False
    if max is not None and root.val >= max:
        return False
    return helper(root.left, min, root.val) and helper(root.right, root.val, max)

执行用时 :60 ms
内存消耗 :16.2 MB

时间复杂度：最坏的情况是遍历所有节点，所以时间复杂度为 O(n)
空间复杂度：空间大小取决于输入二叉树的节点个数 n，所以空间复杂度为 O(n)

参考

https://leetcode-cn.com/problems/validate-binary-search-tree/