Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Solution1.a：Recursive
思路：mid处建立Node，mid左右递归建立左右树
Time Complexity: O(N) Space Complexity: O(logN) 递归缓存
Solution1.b：Recursive
将end作为出界中止位置，而不是最后一个元素
与109同步
Solution1.a Code：
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums.length == 0) {
return null;
}
TreeNode root = helper(nums, 0, nums.length - 1);
return root;
}
private TreeNode helper(int[] nums, int start, int end) {
if(start > end) return null;
int mid = start + (end - start) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = helper(nums, start, mid - 1);
node.right = helper(nums, mid + 1, end);
return node;
}
}
Solution1.b Code：
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums == null || nums.length == 0) return null;
return buildTree(nums, 0, nums.length);
}
private TreeNode buildTree(int[] nums, int start, int end) {
if(start == end) return null;
int mid = start + (end - start) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = buildTree(nums, start, mid);
root.right = buildTree(nums, mid + 1, end);
return root;
}
}
