继续每日一题，今天给大家带来的还是树相关的题目
题目描述
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
题目示例
在这篇文章中：《二叉树的直径》 我通过这道题目给大家说明了如何去思考树类型的题目，文章很短，建议大家可以看一下，针对所有树类型的题目均可通过前中后序遍历去实现，对于本题，首先你要知道什么是BST（二叉搜索树）
对于二叉搜索树的定义很简单，只要一棵树其中序遍历序列是有序序列，我们就认为它是一颗二叉搜索树，如果每个节点的左子树和右子树的高度差不超过 1，那么它就是一棵平衡BST
所以要实现本题，我们需要实现两个功能：
- 构建出来的树其中序序列是有序序列
- 每个节点的左子树和右子树的高度差不能超过 1
上面我一直在强调所有树类型的题目均可以通过BFS（层次遍历） OR DFS（前中后序遍历）去实现，关键就是找到处理节点的时机
对于本题，我们是要构建一个一个的根节点，然后关联其左右子树，所以只能选前序遍历，只有前序遍历，才能满足，先有根节点，然后再构建左右子树，同时题目中给出的条件是升序序列，BST 的中序遍历是升序的，因此我们可以以升序序列中的任一个元素作为根节点，以该元素左边的升序序列构建左子树，以该元素右边的升序序列构建右子树，这样得到的树就是一棵二叉搜索树
这样虽然可以构建BST，但是我们还需要保证平衡，所以只能选择有序数组的中间节点作为起始点，由于总是选择中间元素作为根，左子树和右子树的大小最多相差 1，从而保证树在每个节点处都是平衡的。
具体流程如下：
- 找到数组的中间索引 mid（使用整数除法，向下取整），将 nums[mid] 作为根节点。
- 左子树由 nums 中索引 left 到 mid-1 的子数组构建。
- 右子树由 nums 中索引 mid+1 到 right 的子数组构建。
- 递归基线：如果子数组的起始索引 left 大于结束索引 right，则返回 None（表示空子树）。
重复以上过程构建一个个的节点即可
核心代码如下：
private TreeNode dfs(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = (right + left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = dfs(nums, left, mid - 1);
root.right = dfs(nums, mid + 1, right);
return root;
}
完整代码：
public TreeNode sortedArrayToBST(int[] nums) {
return dfs(nums, 0, nums.length - 1);
}
private TreeNode dfs(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = (right + left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = dfs(nums, left, mid - 1);
root.right = dfs(nums, mid + 1, right);
return root;
}
学会了这道题，后面还有一道关联的题目一起带着大家做一下
题目描述：
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
题目示例：
在上面我已经讲过了什么是BST以及平衡BST，对于本题，我们只需要保证中序遍历的时候当前元素比上一个元素大即可，所以我们需要使用一个变量来维护上一个元素的值
具体实现如下：
static Integer lastNum;
public static boolean isValidBST(TreeNode root) {
lastNum = null;
return dfs(root);
}
private static boolean dfs(TreeNode root) {
if (root == null) {
return true;
}
if (!dfs(root.left)) {
return false;
}
int cuVal = root.val;
if (lastNum != null
&& cuVal <= lastNum) {
return false;
}
lastNum = cuVal;
return dfs(root.right);
}
当然你还可以通过记录中序遍历序列，然后通过该序列是否有序来判断是否是BST，只是该方法需要额外进行一次for循环遍历，无论哪一种方法其本质都是在考察树的前中后序遍历
static List<Integer> list;
public static boolean isValidBST(TreeNode root) {
list = new ArrayList<>();
dfs(root);
for (int i = 1; i < list.size(); i++) {
if (list.get(i) < list.get(i - 1)) {
return false;
}
}
return true;
}
private static void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
list.add(root.val);
dfs(root.right);
}