将有序数组转换为二叉搜索树
难度:
标签:
题目描述
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
示例 1：
输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3] 输出：[3,1] 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104nums按 严格递增 顺序排列
代码结果
运行时间: 80 ms, 内存: 15.8 MB
// 思路：
// 使用Java Stream将有序数组转换为平衡的二叉搜索树。
// 使用IntStream递归地选择数组的中间元素作为根节点。
import java.util.stream.IntStream;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
return buildTree(nums, 0, nums.length - 1);
}
private TreeNode buildTree(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 = buildTree(nums, left, mid - 1);
root.right = buildTree(nums, mid + 1, right);
return root;
}
}
解释
方法:
这个题解使用了递归的方法来将有序数组转换为平衡二叉搜索树。主要思路是：
1. 如果数组为空，返回None。
2. 确定数组的中间元素作为当前子树的根节点。
3. 递归地将数组的左半部分转换为左子树，将右半部分转换为右子树。
4. 返回构建好的根节点。
通过选择数组的中间元素作为根节点，可以保证左右子树的节点数量尽可能平衡，从而构建出平衡二叉搜索树。
时间复杂度:
O(n * log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么将数组中的中间元素选择为根节点有利于构建平衡二叉搜索树？
▷🦆
在递归过程中，是否每次都需要实际分割数组来构建左右子树，还是有其他更高效的方法？
▷🦆
递归构建二叉搜索树时，如果数组长度为偶数，选择中间元素的策略是否有多种，它们对树的平衡有何影响？
▷🦆
在构建平衡二叉搜索树的过程中，如果输入数组不是完全有序或存在重复元素，这会对树的结构产生什么影响？
▷