# LeetCode 29：验证二叉搜索树 Validate Binary Search Tree

### 题目：

Given a binary tree, determine if it is a valid binary search tree (BST).

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

```输入:
2
/ \
1   3

```输入:
5
/ \
1   4
/ \
3   6

### 解题思路：

`node.left.val < node.val < node.right.val`

```    5
/ \
1   7
/ \
4   6```

### Java

```class Solution {
public boolean isValidBST(TreeNode root) {
return helper(root, null, null);
}

private boolean helper(TreeNode node, Integer lower, Integer upper) {
if (node == null)
return true;

int val = node.val;
if (lower != null && val <= lower)
return false;
if (upper != null && val >= upper)
return false;

if (!helper(node.left, lower, val))
return false;
if (!helper(node.right, val, upper))
return false;

return true;
}
}```

### Python

```class Solution:
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def helper(node, lower = float('-inf'), upper = float('inf')):
if not node:
return True

val = node.val
if val <= lower or val >= upper:
return False

if not helper(node.left, lower, val):
return False
if not helper(node.right, val, upper):
return False
return True

return helper(root)```

### Golang

```const lower = math.MinInt64
const upper = math.MaxInt64

func isValidBST(root *TreeNode) bool {
return helper(root, lower, upper)
}

func helper(node *TreeNode, lower, upper int) bool {
if node == nil {
return true
}
val := node.Val
if lower >= val || upper <= val {
return false
}
if !helper(node.Left, lower, val) {
return false
}
if !helper(node.Right, val, upper) {
return false
}
return true
}```

0 条评论

• ### LeetCode98题 验证二叉搜索树（Validate Binary Search Tree）

https://leetcode-cn.com/problems/validate-binary-search-tree/

• ### Js算法与数据结构拾萃（4）：二叉树

因此只要答对这道题，你就可以超越世界级大牛，问鼎码林之巅（逃） 导读： •二叉树知识重点•二叉树深度不一，因此天生适用递归，因此可用递归处理•判断两树相等•翻转...

• ### Python3刷题系列（四）

https://leetcode.com/problems/happy-number/

• ### ​LeetCode刷题实战98：验证二叉搜索树

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就...

• ### LeetCode - 二叉搜索树中的插入操作

原题地址：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

• ### 资源 | 从算法到数据结构，百道面试问题实现答案集合

选自GitHub 作者：Sherali Obidov 机器之心编译 参与：李亚洲、微胖、蒋思源 该资源是算法、数据结构以及面试问题解决方案的集合，里面的 rep...

• ### LeetCode 173. Binary Search Tree Iterator（搜索二叉树）

题解：题目说Next()的时间效率O(1),空间效率O(h),h为树的高度。我们维护一个栈，把前序遍历的左子树的结果存进去。

• ### 二叉树问题（一）-LeetCode 110、617、101、814、655、98、654（递归思路）

给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

• ### 二叉树问题（三）-LeetCode 669、951、662、199、538、236（中序，层次遍历）

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果...

• ### DFS基础问题-LeetCode 98、101（二叉树中序遍历，层次遍历）

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

• ### 【leetcode刷题】T154-二叉搜索树中的插入操作

https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

• ### ​LeetCode刷题实战99：恢复二叉搜索树

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就...

• ### 【leetcode刷题】20T50-验证二叉搜索树

https://leetcode-cn.com/problems/validate-binary-search-tree

• ### LeetCode - 二叉搜索树中的搜索

原题地址：https://leetcode-cn.com/problems/search-in-a-binary-search-tree/

• ### [Leetcode][二叉树]相关题目汇总/分析/总结

前中后三种序列，递归都是一样的理解。迭代的话，前后两个可以互相理解。中序需要单独理解。当然我认为可能我还没有理解透彻。

• ### 【leetcode刷题】T141-把二叉搜索树转化成更大的树

https://leetcode-cncom/problems/convert-bst-to-greater-tree/

• ### 二叉树高频题

Given a binary tree, return the preorder traversal of its nodes' values.

• ### ​LeetCode刷题实战449：序列化和反序列化二叉搜索树

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就...

• ### 二叉树-LeetCode 235、236、226、230（中序，LCA，DFS）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 ...