<reponame>wangkuntian/leetcode<gh_stars>0
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
__project__ =  'leetcode'
__file__    =  '__init__.py'
__author__  =  'king'
__time__    =  '2020/2/13 20:41'


                              _ooOoo_
                             o8888888o
                             88" . "88
                             (| -_- |)
                             O\  =  /O
                          ____/`---'\____
                        .'  \\|     |//  `.
                       /  \\|||  :  |||//  \
                      /  _||||| -:- |||||-  \
                      |   | \\\  -  /// |   |
                      | \_|  ''\---/''  |   |
                      \  .-\__  `-`  ___/-. /
                    ___`. .'  /--.--\  `. . __
                 ."" '<  `.___\_<|>_/___.'  >'"".
                | | :  `- \`.;`\ _ /`;.`/ - ` : | |
                \  \ `-.   \_ __\ /__ _/   .-` /  /
           ======`-.____`-.___\_____/___.-`____.-'======
                              `=---='
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                       佛祖保佑        永无BUG
"""

"""
难度：中等

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

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

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

示例2:

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

from leetcode.lessons.binary_search_tree import TreeNode


class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.valid(root, float('-inf'), float('inf'))

    def valid(self, node, lower, upper):
        if not node:
            return True
        if node.val <= lower or node.val >= upper:
            return False
        return self.valid(node.left, lower, node.val) and \
               self.valid(node.right, node.val, upper)


print(Solution().isValidBST(TreeNode.generate([2, 1, None, None, 3])))
print(Solution().isValidBST(
    TreeNode.generate([5, 1, None, None, 4, 3, None, None, 6])))

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
__project__ =  'leetcode'
__file__    =  '__init__.py'
__author__  =  'king'
__time__    =  '2020/2/13 20:41'


                              _ooOoo_
                             o8888888o
                             88" . "88
                             (| -_- |)
                             O\  =  /O
                          ____/`---'\____
                        .'  \\|     |//  `.
                       /  \\|||  :  |||//  \
                      /  _||||| -:- |||||-  \
                      |   | \\\  -  /// |   |
                      | \_|  ''\---/''  |   |
                      \  .-\__  `-`  ___/-. /
                    ___`. .'  /--.--\  `. . __
                 ."" '<  `.___\_<|>_/___.'  >'"".
                | | :  `- \`.;`\ _ /`;.`/ - ` : | |
                \  \ `-.   \_ __\ /__ _/   .-` /  /
           ======`-.____`-.___\_____/___.-`____.-'======
                              `=---='
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                       佛祖保佑        永无BUG
"""

"""
难度：中等

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

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

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

示例2:

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

from leetcode.lessons.binary_search_tree import TreeNode


class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.valid(root, float('-inf'), float('inf'))

    def valid(self, node, lower, upper):
        if not node:
            return True
        if node.val <= lower or node.val >= upper:
            return False
        return self.valid(node.left, lower, node.val) and \
               self.valid(node.right, node.val, upper)


print(Solution().isValidBST(TreeNode.generate([2, 1, None, None, 3])))
print(Solution().isValidBST(
    TreeNode.generate([5, 1, None, None, 4, 3, None, None, 6])))
#!/usr/bin/env python # -*- coding: utf-8 -*- __project__ =  'leetcode' __file__    =  '__init__.py' __author__  =  'king' __time__    =  '2020/2/13 20:41'                                 _ooOoo_                              o8888888o                              88" . "88                              (| -_- |)                              O\  =  /O                           ____/`---'\____                         .'  \\|     |//  `.                        /  \\|||  :  |||//  \                       /  _||||| -:- |||||-  \                       |   | \\\  -  /// |   |                       | \_|  ''\---/''  |   |                       \  .-\__  `-`  ___/-. /                     ___`. .'  /--.--\  `. . __                  ."" '<  `.___\_<|>_/___.'  >'"".                 | | :  `- \`.;`\ _ /`;.`/ - ` : | |                 \  \ `-.   \_ __\ /__ _/   .-` /  /            ======`-.____`-.___\_____/___.-`____.-'======                               `=---='           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^                        佛祖保佑        永无BUG 难度：中等  给定一个二叉树，判断其是否是一个有效的二叉搜索树。  假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。  示例1: 输入:     2    / \   1   3 输出: true  示例2:  输入:     5    / \   1   4     / \    3   6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。     根节点的值为 5 ，但是其右子节点值为 4 。 :type root: TreeNode         :rtype: bool