给你一个二叉树的根节点 root
,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
![](https://github.xin/wp-content/uploads/2023/07/f36c4d1e6841575-1.jpg)
输入:root = [2,1,3] 输出:true
示例 2:
![](https://github.xin/wp-content/uploads/2023/07/3b9952141328bc4-1.jpg)
输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
- 树中节点数目范围在
[1, 104]
内 -231 <= Node.val <= 231 - 1
题解:
递归法:
func isValidBST(root *TreeNode) bool {
return helper(root, math.MinInt64, math.MaxInt64)
}
func helper(node *TreeNode, lower, upper int) bool {
if node == nil {
return true
}
if node.Val <= lower || node.Val >= upper {
return false
}
return helper(node.Left, lower, node.Val) && helper(node.Right, node.Val, upper)
}
递归法+中序遍历法:
func isValidBST(root *TreeNode) bool {
var prev *TreeNode
var travel func(node *TreeNode) bool
travel = func(node *TreeNode) bool {
if node == nil {
return true
}
leftResult := travel(node.Left)
// 因为二叉搜索树的特性,左边的最小,根部其次,右边最大
// 中序遍历的顺序正好是 左 中 右
// 所以只要 node.Val 一直大于 prev.Val 就是正确的
// 反 node.Val 小于或等于 prev.Val 了就可以判定这不是一个合格的二叉搜索树
if prev != nil && node.Val <= prev.Val {
return false
}
prev = node
rightResult := travel(node.Right)
return leftResult && rightResult
}
return travel(root)
}
评论前必须登录!
注册