# \[面试题 04.05]\[中等]\[DFS] 合法二叉搜索树

## 题目描述

[面试题 04.05. 合法二叉搜索树](https://leetcode-cn.com/problems/legal-binary-search-tree-lcci/)

实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例 1:

```
输入:
    2
   / \
  1   3
输出: true
```

示例 2:

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

## 解题思路

两种思路:

1. 检查当前节点的值, 是否比左子树的最大值大(或不小于该最大值, 我们认为相等的数, 应当放在左边), 比右子树的最小值小
2. **中序遍历**整棵树, 得到的遍历序列**必须是递增的**, 才是二叉搜索树

下面的代码采用第一种思路.

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def dfs(node):
            if node is None:
                return float('inf'), float('-inf')

            lmin, lmax = dfs(node.left)
            if lmin is False:
                return False, False
            rmin, rmax = dfs(node.right)
            if rmin is False:
                return False, False

            if node.val <= lmax or node.val >= rmin:
                return False, False
            return max(node.val, lmax), min(node.val, rmin)

        fmin, fmax = dfs(root)
        return True if fmin is not False else False
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/shu/04.05-he-fa-er-cha-sou-suo-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.