# 验证二叉查找树

描述

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

```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/qiang-hua-4-shuang-zhi-zhen-ff09/yan-zheng-er-cha-cha-zhao-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.