> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/qiang-hua-4-shuang-zhi-zhen-ff09/yan-zheng-er-cha-cha-zhao-shu.md).

# 验证二叉查找树

描述

给定一个二叉树，判断它是否是合法的二叉查找树(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)
        
        
        

```
````