Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
- 要求把一个有序数组转换成一颗二分查找树。
- 其实从本质来看，如果把一个数组看成一棵树（以中点为根，左右为左右子树，依次下去）数组就等价于一个二分查找树。
- 构造这棵树，那就把中间元素转化为根，然后递归构造左右子树。
- 所以我们还是用二叉树递归的方法来实现，以根作为返回值，每层递归函数取中间元素作为当前根； 然后左右结点接上左右区间的递归函数返回值。
- 时间复杂度还是一次树遍历O(n)，总的空间复杂度是栈空间O(logn)加上结果的空间O(n)，额外空间是O(logn)，总体是O(n)。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
//用二分的方法，因为array是已经sorted了的，所以取mid的数就可以做root。比如【1，2，3，4，5】
TreeNode result = helper(nums, 0, nums.length - 1);
return result;
}
private TreeNode helper(int[] nums, int start, int end) {
if (start > end) return null;
//mid的数为root
int mid = start + (end - start) / 2;
TreeNode cur = new TreeNode(nums[mid]);
//root.left是以mid左边的数组重新计算
cur.left = helper(nums, start, mid - 1);
//root.right是以mid右边的数组重新计算
cur.right = helper(nums, mid + 1, end);
//最后返回root即可
System.out.println(cur.val);
return cur;
}
}
