【每日力扣】98. 验证二叉搜索树 与 108. 将有序数组转换为二叉搜索树

🔥 个人主页: 黑洞晓威
😀你不必等到非常厉害，才敢开始，你需要开始，才会变的非常厉害

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左

  子树

  只包含

  小于

  当前节点的数。

• 节点的右子树只包含 大于 当前节点的数。

• 所有左子树和右子树自身必须也是二叉搜索树。

解题思路

1. 利用递归检查每个节点是否在正确的范围内。
2. 对于左子树，它的值范围为负无穷到根节点值。
3. 对于右子树，它的值范围为根节点值到正无穷。
4. 每个节点带有上下界（最小值和最大值），在遍历节点时更新这些上下界。

代码实现

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 ，其中元素已经按 升序 排列，请你将其转换为一棵

平衡二叉搜索树。

解题思路

1. 找到数组的中间元素作为根节点。
2. 数组被中间元素分成了左右两部分，分别递归构建左子树和右子树。
3. 递归的结束条件是左边界大于右边界，此时返回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;}
}