原题
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
解法
思想
类似于二分查找，每次递归使用数组的中间元素作为根节点。就能最大化利用左右节点空间，使之平衡。
代码
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBST(nums, 0, nums.length);
}
private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
if (start == end) {
return null;
}
int mid = (start + end) >>> 1;
TreeNode root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums, start, mid);
root.right = sortedArrayToBST(nums, mid + 1, end);
return root;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode108-%e5%b0%86%e6%9c%89%e5%ba%8f%e6%95%b0%e7%bb%84%e8%bd%ac%e6%8d%a2%e4%b8%ba%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91/
相关推荐
-
leetcode3-无重复字符的最长子串
原题 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例1： 输入： "abcabcbb" 输出： 3 解释： 因为无重复字符的最长子串是 "abc"，所以其长...
-
leetcode540-有序数组中的单一元素
原题 给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。 示例1: 输入： [1,1,2,3,3,4,4,8,8] 输出： 2 示例2: 输入...
-
leetcode779-第K个语法符号
原题 在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。 给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始） 例子： 输入: N...
-
leetcode191-位1的个数
原题 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。 示例 1： 输入： 000000000000000000000000...
-
leetcode162-寻找峰值
原题 峰值元素是指其值大于左右相邻值的元素。 给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。 数组可能包含多个峰值，在这种情况...
-
leetcode121-买卖股票的最佳时机
原题 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在...
-
leetcode102-二叉树的层次遍历
原题 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如:给定二叉树: [3,9,20,null,null,15,7],  ...
-
leetcode59-螺旋矩阵II
原题 给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, ...
-
蓝桥杯试题-小数第n位
原题 资源限制 时间限制：1.0s 内存限制：256.0MB 问题描述 我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。 如果我们把有限小数的末尾加上无限多个...
-
leetcode88-合并两个有序数组
原题 给定两个有序整数数组 nums1 和 nums2 ，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。 说明： 初始化 nums1 和 nums2 的...
