This is NO.108 problem in leetcode.
The description of this problem is:
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
This problem is not hard, I had a simple thought quickly. But I always made memory limit error.
For sum up, I think I need to remember some points to avoid making them again.
- I should make sure that I connect each node correcly, in this problem, I need to create root in my helper function as well.
- I need to move idx after each manipulating.
- I need to set the correct falg to terminal program, like min > max in this problem.
Code is below:
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length == 0){
return null;
}
return createBST(nums,0, nums.length-1);
}
TreeNode createBST(int[] nums, int start, int end){
if(start>end){
return null;
}
int mid = (start+end)/2;
TreeNode node = new TreeNode(nums[mid]);
node.left = createBST(nums, start,mid-1);
node.right = createBST(nums, mid+1,end);
return node;
}
}