Leetcode: Convert sorted array to binary search tree

09/25/2015

First practice on 08/25/2015

108  Convert sorted array to binary search tree (No. 108)

Julia's C# implementation: top-down approach 

https://github.com/jianminchen/Leetcode_C-/blob/master/108ConvertSortedArrayToBinarySearchTree.cs

9/25/2015 Try to add some fun memory about top-down approach for binary search tree construction, then, present some diagrams. 

my task is to make the coding practice more fun, and some funny part with naive drawing. Maybe, Julia could use the drawing to bring some comic style to serious coding challenges. 

Julia's favorite blogs about this leetcode question: 

1. https://gist.github.com/Jeffwan/8982109

Read this blog (1) and like the analysis, first time see the comment: "Conquer" above the return statement:

return node; Learn Divide and Conquer in this simple illustration. 

2. http://blog.csdn.net/linhuanmars/article/details/23904883

Because this blog's popularity, it is one of my favorites. One thing I like to discuss is about the base case, how this base case is making sense, and then mimimum/ no redundancy. Let Julia argue about it. 

Here is the code in the above blog:

1. private TreeNode helper(int[] num, int l, int r)  
2. {  
3.     if(l>r)  
4.         return null;  
5.     int m = (l+r)/2;  
6.     TreeNode root = new TreeNode(num[m]);  
7.     root.left = helper(num,l,m-1);  
8.     root.right = helper(num,m+1,r);  
9.     return root;  
10. }  

Have some base case debates, and make this algorithm more entertainment: 

why base case is: 

 if(l>r) return null, 

if l==r, the above function will perform: 

 root = new TreeNode(num[l]), and also, 

set up 

root.left = RecursiveFunctionCall()  -> go to base case, return null, 

root.right  is the same as root.left, 

and then return root; 

how come it is not: 

 if(l==r) return new TreeNode(num[l])

then, need to add checking before the helper call:
if(l<=m-1) 

  root.left = helper(num, l, m-1)

if(m+1<=r)

  root.right = helper(num, m+1, r)

So, better to leave this if conditional checking to base case; at least there are 2 if checking, anyone of them implies l<=r, so duplicate checking. 

3. http://www.acmerblog.com/leetcode-solution-convert-sorted-array-to-binary-search-tree-6247.html

julia's comment: 

the base case has redundant line:

Java code:

if(start == end) return new TreeNode(num[start]);




Here is the Java code: 




public class Solution {

11	public static TreeNode sortedArrayToBST(int[] num) {

12	if(num == null || num.length == 0) return null;

13	return sortedArrayToBST(num, 0, num.length-1);

14

}

15

16	public static TreeNode sortedArrayToBST(int num[],int start, int end){

17	if(start > end ) return null;

18	if(start == end) return new TreeNode(num[start]);

19	int mid = start + (end-start)/2;

20	TreeNode root = new TreeNode(num[mid]);

21	root.left = sortedArrayToBST(num, start, mid-1);

22	root.right = sortedArrayToBST(num, mid+1, end);

23	return root;

24

}

25

}

4. http://pisxw.com/algorithm/Convert-Sorted-Array-to-Binary-Search-Tree.html

Remind me the BST, the left and right subtree difference is maximum 1. 

5. http://www.kunxi.org/notes/LeetCode/

Look into the leetcode solution later. Should be a great one for me to catch up some programming tips.