本文主要是介绍【每日力扣】98. 验证二叉搜索树 与 108. 将有序数组转换为二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
🔥 个人主页: 黑洞晓威
😀你不必等到非常厉害,才敢开始,你需要开始,才会变的非常厉害
98. 验证二叉搜索树
给你一个二叉树的根节点 root
,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
-
节点的左
子树
只包含
小于
当前节点的数。
-
节点的右子树只包含 大于 当前节点的数。
-
所有左子树和右子树自身必须也是二叉搜索树。
解题思路
- 利用递归检查每个节点是否在正确的范围内。
- 对于左子树,它的值范围为负无穷到根节点值。
- 对于右子树,它的值范围为根节点值到正无穷。
- 每个节点带有上下界(最小值和最大值),在遍历节点时更新这些上下界。
代码实现
class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}private boolean isValidBST(TreeNode node, long min, long max) {if (node == null) {return true;}if (node.val <= min || node.val >= max) {return false;}return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);}
}
108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums
,其中元素已经按 升序 排列,请你将其转换为一棵
平衡二叉搜索树。
解题思路
- 找到数组的中间元素作为根节点。
- 数组被中间元素分成了左右两部分,分别递归构建左子树和右子树。
- 递归的结束条件是左边界大于右边界,此时返回null。
代码实现
class Solution {public TreeNode sortedArrayToBST(int[] nums) {if (nums == null || nums.length == 0) {return null;}return constructBST(nums, 0, nums.length - 1);}private TreeNode constructBST(int[] nums, int left, int right) {if (left > right) {return null;}int mid = left + (right - left) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = constructBST(nums, left, mid - 1);root.right = constructBST(nums, mid + 1, right);return root;}
}
这篇关于【每日力扣】98. 验证二叉搜索树 与 108. 将有序数组转换为二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!