Tuesday, March 17, 2015

108. Convert Sorted Array to Binary Search Tree Leetcode Java

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Solution:
For a height balanced BST, the root will the middle element of the sorted array. Because, if we perform an in-order traversal of the height balanced BST, the left nodes and the right nodes will be well distributed on the two sides of the root. 
The solution is pick the middle element of the array, and recursively construct the left subtree, and right subtree. 


  public TreeNode sortedArrayToBST(int[] num) {  
     if(num==null) return null;  
     return helper(num,0,num.length-1);  
   }  
   public TreeNode helper(int[] num, int start, int end){  
     if(start>end) return null;  
     int m=(end-start)/2+start;  
     TreeNode root=new TreeNode(num[m]);  
     root.left=helper(num,start,m-1);  
     root.right=helper(num,m+1,end);  
     return root;  
   }  

No comments:

Post a Comment