Sept.
22, 2015
109
Convert sorted list to binary search tree (No. 109)
8/25/2015
Read
the following blogs:
C#,
bottom up, time O(n), space O(log n) solution - best solution:
C#,
top down, time O(n^2), space O(long n) solution - naive solution:
worked
on code 2 times, first time, the calculation is kind of messy, then, worked on
Leetcode question 108, get the idea to make it more simple; tips like len/2
only shows once, afterwards, use m instead. Just need to improve coding, think
to make it more abstract, simple.
9/21/2015
Review
the best solution, and then, totally forgot the bottom up solution idea. So,
update the code with more comment.
Need
to review more about bottom up/ top down solution in tree problems. Get more
experience on bottom-up solution, read some articles about it.
9/22/2015
Go
over one example to build some muscle memory about this bottom up, O(1)
solution to find the root node in subtree function.
Sorted
List:
1->2->3->4->5->6->7,
How
to convert the above sorted list to a binary search tree?
Thought
process:
1. First, get length of the list, which
is 7 in the above list;
2. Secondly, define a recursive function
called
constructBST(ref
TreeNode head, int start, int end)
the
above function definition, 3 arguments:
1. First one is the reference of head
node of sorted list,
2. Start index of the list,
3. End index of the list
In
the function, first define the base case:
head
is null, or start<end, return null
start==end,
return head
then,
call the recursive function for left subtree:
head
node is the same, start is the same, but end is len/2-1;
great
tip comes in, the head node should move in the function, so that
root
node can be accessed in the list using O(1), instead of starting from very
beginning.
One
more statement:
head
= head.next;
TreeNode
root = head; // return this node as tree root node
Root.left
= left subtree root node
Root.right
= right subtree recursive function
constructBST(ref head.next, mid+1, end)
The
tips to remember in the design, the recursive function should return the root
node of the tree; secondly, input argument of linked list should use reference,
and also head node moves in the recursive function, so it is O(1) to find the
root node.
Just
cannot believe that only call .next function once in the recursive function!
How to argue that the move is only once? Therefore, the total calls of .next
should be length of list. Total recursive function calls is n, length of
list.
Debate why the recursive function has to return root node, and set up root
node, connect its left/ right subtree root node.
Debate why the linked list head node is moving.
设计这个递归函数, 如何避免从链的头开始访问, 到中间点? 最关键是让链的头移动, 当需要设计树的根节点, 只要移动一步, 就是根节点. 画一个图, 帮助自己理解记忆; 看一篇文章, 开拓思路.
The main point to understand the best solution using O(ln N) space, the left subtree has to be built first, and then, head node can be retrieved as .next method call, root node can be set up, and then, left subtree can be built. So, left subtree, then right subtree, then the tree with root node. Bottom up.
Whereas sorted array to BST, the root node can be find right away, and then, tree can be set up top down. Julia is still confusing this top down / bottom up difference. :-) read more blogs.
Blogs:
1. use global variable to remember the head node of linked list, great idea:
2. another implementation using two pointers. Try it using C# later.
3. Java implementation, teach me how to use reference in Java or wrapper class. Good point!
4.
Time and space complexity analysis - think about it - very clear analysis
5. Three implementation discussions
6. Great explanation - bottom up / top down, and in order traversal/ post order traversal
Implement the above 6 blogs using C#, and then, share the blog. After 1 month, check again and see if I can come out the bottom up solution in 5 minutes. If yes, stop; otherwise review again.
Dec. 24, 2015
Review the solution again.
How to recall the solution step by step?
1. Get list length <- travel the list once
2. Design the recursive function with a list, start and end two position; use the position of start/end to boundary case checking; also the function returns the root node of the tree.
3. Build left subtree
4. Find the middle of list as root <- how to get there?
Cannot traverse the list again to half length if you want optimized solution, since it is in recursive function, O(nlogn)
Every recursive call the list pointer will traverse once
5. Connect root node to left child
6. Move list pointer to next one
7. Build right subtree
connect root node to right child as well.
Recap the importance of function design:
1. list with a pointer moving, starting from head
2. start, end position of linked list
3. in the function build a tree
4. return root node of the tree
