108. Convert Sorted Array to Binary Search Tree
Last updated
Last updated
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}/**
* Time complexity : O(N) since we visit each node exactly once.
* Space complexity : O(N) to keep the output, and O(logN) for the
* recursion stack.
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums == null || nums.length == 0) return null;
return sortedArrayToBST(nums, 0, nums.length-1);
}
private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
if(start > end) return null;
int index = (start + end)/2;
TreeNode node = new TreeNode(nums[index]);
node.left = sortedArrayToBST(nums, start, index-1);
node.right = sortedArrayToBST(nums, index+1, end);
return node;
}
}