Question
Formatted question description: https://leetcode.ca/all/108.html
108 Convert Sorted Array to Binary
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
@tag-tree
Algorithm
The root node should be the middle point of the ordered array, separated from the middle point into two left and right ordered arrays, and find out the left and right child nodes whose middle point is the original middle point.
Code
Java
import java.util.Arrays;
public class Convert_Sorted_Array_to_Binary_Search_Tree {
public static void main(String[] args) {
Convert_Sorted_Array_to_Binary_Search_Tree out = new Convert_Sorted_Array_to_Binary_Search_Tree();
Solution s = out.new Solution();
int[] a = {1, 2, 3, 4, 5};
int[] b = Arrays.copyOfRange(a, 0, a.length);
System.out.println(Arrays.toString(b));
// b = Arrays.copyOfRange(a, 2, 1); // error, must to > from
b = Arrays.copyOfRange(a, 2, 2); // ok, empty array returned
System.out.println("a, 2, 2: " + Arrays.toString(b));
// b = Arrays.copyOfRange(a, -1, 10); // error, out of boundary
// System.out.println("a, -1, 10" + Arrays.toString(b));
b = Arrays.copyOfRange(a, a.length, a.length); // ok, empty array returned
System.out.println("a, a.length, a.length: " + Arrays.toString(b));
}
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) return null;
return dfs(nums, 0, nums.length - 1);
}
TreeNode dfs(int[] nums, int left, int right) {
if (left > right) return null;
int mid = left + (right - left) / 2;
TreeNode cur = new TreeNode(nums[mid]);
cur.left = dfs(nums, left, mid - 1);
cur.right = dfs(nums, mid + 1, right);
return cur;
}
}
}