Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Balanced tree : 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.
Example :
Given A : [1, 2, 3]
A height balanced BST :
2
/ \
1 3
Method:
The mid element is the root
Solution:
Time: O(n) Space: O(n)
/** * Definition for binary tree * class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { * val = x; * left=null; * right=null; * } * } */ public class Solution { // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY public TreeNode sortedArrayToBST(final List<Integer> A) { if (A.size() == 0) return null; int mid = A.size() / 2; TreeNode root = new TreeNode(A.get(mid)); root.left = sortedArrayToBST(A.subList(0, mid)); root.right = sortedArrayToBST(A.subList(mid + 1, A.size())); return root; } }