【每日力扣】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;}
}