树与图简单1 种解法
#108将有序数组转换为二叉搜索树
把升序数组转换为一棵高度平衡二叉搜索树。
#二叉搜索树#分治#数组
原题
给你一个整数数组 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按 严格递增 顺序排列
解题主线
- 每次选择区间中点作为根，可让左右子树规模最多相差一。
解法 1：中点分治
递归用中点建立根，并处理左右半区间。
-
时间复杂度： O(n)
-
空间复杂度： O(log n)，递归栈；不计输出树
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int left, int right) {
// [left, right] 为空时结束递归，也是叶子节点子树的边界。
if (left > right) return null;
// 中点作为根保证左右区间规模最多相差一，并维持中序序列有序。
int middle = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[middle]);
root.left = build(nums, left, middle - 1);
root.right = build(nums, middle + 1, right);
return root;
}
}边界与易错点
- 空区间条件是 left > right。
- 中点用 left + (right - left) / 2 避免溢出。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q108_sortedArrayToBST.java