给定一个二叉树,判断其是否是一个有效的二叉搜索树。
Given a binary tree, determine if it is a valid binary search tree (BST).
假设一个二叉搜索树具有如下特征:
Assume a BST is defined as follows:
示例 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
,代码很简单如下:
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; } }
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)
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 }
本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug
原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。
原始发表时间:2020-03-09
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句