Solution 1: do it iteratively. --- working in progress, the below implementation is not correct!!!
public static Node sorted2bstIteratively(int[] nums){
assert(nums != null);
int start = 0, end = nums.length-1, mid = (start + end)>>>1;
Node root, pre;
root = pre = new Node(nums[mid]);
end = mid -1;
while(start<=end){
mid = (start + end)>>>1;
Node n = new Node(nums[mid]);
pre.left = n;
pre = n;
end = mid - 1;
}
pre = root;
start = (nums.length-1)>>>1+1; end = nums.length-1;
while(start<=end){
mid = (start + end)>>>1;
Node n = new Node(nums[mid]);
if(pre!=null)
pre.right = n;
pre = n;
pre = n;
start = mid + 1;
}
return root;
}
Solution 2: do it recursively.
public static Node sorted2bst(int[] nums){
assert(nums != null);
return sorted2bstRec(nums, 0, nums.length-1);
}
public static Node sorted2bstRec(int[] nums, int start, int end){
if(start>end)
return null;
int mid = (start+end)>>>1;
Node curr = new Node(nums[mid]);
curr.left = sorted2bstRec(nums, start, mid-1);
curr.right = sorted2bstRec(nums, mid+1, end);
return curr;
}
it would be very good idea to use iteration to create bst. But I tried { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, it seems the tree is not correct.
ReplyDelete