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
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:
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.
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:
- private TreeNode helper(int[] num, int l, int r)
- {
- if(l>r)
- return null;
- int m = (l+r)/2;
- TreeNode root = new TreeNode(num[m]);
- root.left = helper(num,l,m-1);
- root.right = helper(num,m+1,r);
- return root;
- }
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.
julia's comment:
the base case has redundant line:
Java code:
if(start == end) return new TreeNode(num[start]);
Here is the Java code:
11 | public static TreeNode sortedArrayToBST(int[] num) { |
12 | if(num == null || num.length == 0) return null; |
13 | return sortedArrayToBST(num, 0, num.length-1); |
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); |
Remind me the BST, the left and right subtree difference is maximum 1.
Look into the leetcode solution later. Should be a great one for me to catch up some programming tips.
