验证二叉查找树

https://www.lintcode.com/problem/95/description?utm_source=sc-cheatsheet-cyc

描述

给定一个二叉树，判断它是否是合法的二叉查找树(BST)

一棵BST定义为：

• 节点的左子树中的值要严格小于该节点的值。

• 节点的右子树中的值要严格大于该节点的值。

• 左右子树也必须是二叉查找树。

• 一个节点的树也是二叉查找树。

样例

样例 1：

输入：

tree = {-1}

输出：

true

解释：

二叉树如下(仅有一个节点）:        -1这是二叉查找树。

样例 2：

输入：

tree = {2,1,4,#,#,3,5}

输出：

true

解释：

        二叉树如下：          2         / \        1   4           / \          3   5这是二叉查找树。

解题思路：

我们需要判断给定的树是否是二叉查找树（BST）。二叉查找树的定义是：对于树中的每个节点，左子树所有节点的值都小于该节点的值，而右子树所有节点的值都大于该节点的值。所以把该节点的值作为upper and lower bound传入

可以通过递归来验证每个节点，使其满足这两个条件：

1. 检查节点的左子树，确保所有节点值都小于当前节点值。

2. 检查节点的右子树，确保所有节点值都大于当前节点值。

```python
from lintcode import (
    TreeNode,
)

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: The root of binary tree.
    @return: True if the binary tree is BST, or false
    """

    def is_valid_b_s_t(self, root: TreeNode) -> bool:
        # write your code here       
        return self.helper(root, float('inf'), float('-inf'))

    def helper(self, root: TreeNode, upper: int, lower:int) -> bool:
        if not root:
            return True
        if root.val >= upper or root.val <= lower:#
            return False
        return self.helper(root.left, root.val, lower) and self.helper(root.right, upper, root.val)
        
        
        

```