[98] Validate Binary Search Tree

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

• algorithms
• Medium (24.74%)
• Source Code: 98.validate-binary-search-tree.py
• Total Accepted: 385.4K
• Total Submissions: 1.5M
• Testcase Example: '[2,1,3]'

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Example 1:

Input: 2 /
1 3 Output: true

Example 2:

5

/
1 4   /
  3 6 Output: false Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value   is 5 but its right child's value is 4.

# 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
        """
        if not root: return True
        ret = []

        def inorder(root):
            if not root: return
            if root.left:
                inorder(root.left)
            ret.append(root.val)
            if root.right:
                inorder(root.right)

        inorder(root)

        lenr = len(ret)
        for i in range(1, lenr):
            if ret[i] <= ret[i-1]: return False

        return True