本文主要是介绍Leetcode JAVA刷刷站(98)验证二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目概述
二、思路方向
在Java中,要判断一个二叉树是否是有效的二叉搜索树(BST),我们可以采用递归的方法,通过维护一个外部的范围(通常是
Integer.MIN_VALUE
到Integer.MAX_VALUE
作为初始范围),来确保每个节点的值都在其左子树所有节点值的右侧,并且在其右子树所有节点值的左侧。
三、代码实现
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }
} public class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean isValidBST(TreeNode node, long minVal, long maxVal) { if (node == null) { return true; } // 检查当前节点的值是否在允许的范围内 if (node.val <= minVal || node.val >= maxVal) { return false; } // 递归检查左子树和右子树 return isValidBST(node.left, minVal, node.val) && isValidBST(node.right, node.val, maxVal); }
}
解释
递归函数定义:
isValidBST(TreeNode node, long minVal, long maxVal)
是一个递归函数,它接收一个节点以及一个范围(由minVal
和maxVal
表示)。这个范围用于检查当前节点的值是否合法(即大于minVal
且小于maxVal
)。边界条件:
- 如果当前节点为空,则认为是有效的BST(因为空树是BST的一个特例)。
节点值检查:
- 检查当前节点的值是否小于
maxVal
且大于minVal
。如果不是,返回false
。递归调用:
- 递归地检查左子树,此时范围更新为
(minVal, node.val)
(即左子树中所有节点的值必须小于当前节点的值)。- 递归地检查右子树,此时范围更新为
(node.val, maxVal)
(即右子树中所有节点的值必须大于当前节点的值)。返回值:
- 如果左子树和右子树都是有效的BST,则返回
true
;否则返回false
执行结果:
四、小结
注意,这里将minVal
和maxVal
的类型设为long
,是为了避免在比较时可能出现的整数溢出问题。特别是当树中节点的值接近Integer.MAX_VALUE
时,与其进行比较的下一个更大的整数将会溢出。通过使用long
类型,我们可以避免这个问题。
结语
我宁愿坚强得让人妒忌
也不会懦弱得让人可怜
!!!
这篇关于Leetcode JAVA刷刷站(98)验证二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!