108 - Convert Sorted Array to Binary Search Tree
Written on October 21, 2015
Tweet
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
public class Solution {
/**
* @param A: an integer array
* @return: a tree node
*/
public TreeNode sortedArrayToBST(int[] A) {
if (A == null || A.length == 0) return null;
return sortedArrayToBSTUtil(A, 0, A.length - 1);
}
public TreeNode sortedArrayToBSTUtil(int[] A, int start, int end) {
if (start > end) return null;
int mid = start + (end - start) / 2;
TreeNode root = new TreeNode(A[mid]);
root.left = sortedArrayToBSTUtil(A, start, mid - 1);
root.right = sortedArrayToBSTUtil(A, mid + 1, end);
return root;
}
}
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return
return self.helper(nums, 0, len(nums) - 1)
def helper(self, nums, left, right):
if left > right:
return
mid = (left + right) // 2
root = TreeNode(nums[mid])
root.left = self.helper(nums, left, mid - 1)
root.right = self.helper(nums, mid + 1, right)
return root