LeetCode 29：验证二叉搜索树 Validate Binary Search Tree
LeetCode 29：验证二叉搜索树 Validate Binary Search Tree
爱写bug
发布于 2020-03-12 20:10:44
发布于 2020-03-12 20:10:44
题目：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
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.
示例 1:
输入:
2
/ \
1 3
输出: true示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。解题思路：
刚看的时候以为只要满足任一结点值均大于左子结点，小于右子结点就是二叉搜索树：
node.left.val < node.val < node.right.val
实际上还有一个条件：每个结点的值应当大于其左子树任一结点值，小于其右子树任意结点值。如下二叉树：
5
/ \
1 7
/ \
4 6该二叉树其中任一结点值均大于左子结点，小于右子结点，但并非二叉搜索树，因为结点 4 小于结点 5。
实际上只要记录结点值与上界和下界，满足 lower < node.val < upper，代码很简单如下：
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
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-03-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录