Leetcode 109: convert sorted list to a binary search tree

Sept. 22, 2015

109 Convert sorted list to binary search tree (No. 109)

8/25/2015

Read the following blogs:

http://articles.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

C#, bottom up, time O(n), space O(log n) solution - best solution:

https://github.com/jianminchen/Leetcode_C-/blob/master/109ConvertSortedListToBinarySearchTreeB.cs

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.

https://github.com/jianminchen/Leetcode_C-/blob/master/109ConvertSortedListToBinarySearchTreeC.cs

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:

http://www.jiuzhang.com/solutions/convert-sorted-list-to-binary-search-tree/

2. another implementation using two pointers. Try it using C# later. 

https://siddontang.gitbooks.io/leetcode-solution/content/tree/convert_sorted_listarray_to_binary_search_tree.html

3. Java implementation, teach me how to use reference in Java or wrapper class. Good point!

http://rleetcode.blogspot.ca/2014/02/convert-sorted-list-to-binary-search.html

4. Time and space complexity analysis - think about it - very clear analysis 

http://blog.unieagle.net/2012/12/14/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Aconvert-sorted-list-to-binary-search-tree/

5. Three implementation discussions 

http://www.cnblogs.com/feiling/p/3267917.html

6. Great explanation - bottom up / top down, and in order traversal/ post order traversal

https://leetcodenotes.wordpress.com/2013/11/23/convert-sorted-list-to-binary-search-tree/

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

Java Script, C# learning - reading / videos material

September 21, 2015

First, share my favorite two verses to encourage myself to work harder, and continue to pursuit efforts in JavaScript/ C# / CSS/ other technologies learning in my career. I should have more organized, I just copied all my posts from my facebook and documented in a blog in Google+. Review them, and get more reading / study done continuously while practicing Leetcode questions.

2014年年初开始, 想加强自己JavaScript的经历. 每天学习JavaScript, 6个月之后, 发现自己有好多想法, 重写一部分代码, 有很多想法. 第一次体会到, 只有不停学习, 才能有提高.

From the beginning of 2014, I spent over 12 months to learn JavaScript; Try to explore all I can learn in JavaScript, expose myself to all the best teachers, reading /videos in the world. Learn how smart people are in this technology world, JavaScript area. First time, I did slow down everything to learn a functional programming language.

After 6 - 8 months, I found out that I start to generate ideas to rewrite the Javascript wrote before.

So, document my learning experience and help myself to move forward when I have time.

June 1, 2015
Share the video. I read chinese blog in wechat, and then, catch up this one in English.
CHM Revolutionaries: " How Google Works" Eric Schmidt & Jonathan Rosenberg 

https://www.youtube.com/attribution_link?a=s1oxvH9-h4E&u=%2Fwatch%3Fv%3D3tNpYpcU5s4%26feature%3Dshare

March 15, 2015

So relax and also learn something on Sunday morning. Ajax and async.

https://sec.ch9.ms/ch9/03b0/3ac5c264-043f-4ffd-b2ee-422f39ba03b0/IntroTojQueryM06_mid.mp4


February 22, 2015
Spent half hour on CSS preprocessor. Great topic, and think about benefits to use it.

http://channel9.msdn.com/Series/Adding-Style-with-CSS/06?wt.mc_id=EntriesInArea

Enjoyed one hour video about CSS transition and transformation. Sunday is such great time
to learn something, and then, go out to play sports in Vancouver.

http://channel9.msdn.com/Series/Adding-Style-with-CSS/05

Being a web developer, it is fun to learn something called transition, transformation; Great video.

http://channel9.msdn.com/Series/Adding-Style-with-CSS/05?fb_action_ids=823960460986167&fb_action_types=og.likes&fb_source=other_multiline&action_object_map=%5B771052266276726%5D&action_type_map=%5B%22og.likes%22%5D&action_ref_map=%5B%5D


February 9, 2015

Cooking time - learn something.

http://channel9.msdn.com/Series/Introduction-to-jQuery/02?wt.mc_id=player

February 7, 2015

Will have good time this weekend. Try to watch series video about single page application.

http://channel9.msdn.com/Series/Single-Page-Applications-with-jQuery-or-AngularJS/02?wt.mc_id=EntriesInArea

February 6, 2015

My favorite tip learned today. Learned a few tips, peek definition is also my favorite.

http://channel9.msdn.com/Series/vstips/lazycodesnippets?wt.mc_id=player

February 5, 2015

My Thursday night study time, Java Script is a good choice.

http://channel9.msdn.com/Shows/Defrag-Tools/Defrag-Tools-37-JavaScript-Part-1?wt.mc_id=EntriesInArea

February 1, 2015

My favorite video this Sunday. Learn LINQ, good framework. Save time to develop.

http://www.youtube.com/watch?v=tGr6xm9nUm4&feature=share&fb_ref=share

January 31, 2015

Saturday morning video. Nice to learn a few things, portable library is one.

Programming in C# ( 6 of 8) Splitting Assemblies, WINMD, Diagnostics and Instrumentation

http://youtu.be/ypdnMpR5jZ8

January 26, 2015

Watch the video and learn something new.

Programming in C# (1/8) OOP, Managaged Languages and C#

January 26, 2015

Share the video I like to watch. To test java script is new thing to learn.


http://www.youtube.com/watch?v=yRMsxyGsez4&list=PLfXiENmg6yyUpIVY9XVOkbdmBPx6PUm9_&feature=share&index=3&fb_ref=share

Netflix: Stop Making Excuses and Start Testing Your JavaScript!

http://goo.gl/QBWjvA

January 25, 2015
Sunday morning video, relax me and then learn something about Javascript.

Netflix JavaScript Talks - Async JavaScript with Reactive Extensions

http://www.youtube.com/attribution_link?a=LtVczHAKqbM&u=%2Fwatch%3Fv%3DXRYN2xt11Ek%26feature%3Dshare&fb_ref=share

January 23, 2015

Study time, good presentation!

Netflix JavaScript Talks - Version 7: The Evolution of JavaScript

http://www.youtube.com/watch?v=DqMFX91ToLw&feature=share&fb_ref=share

January 22, 2015

So easy to find an advance topic about java script through youtube, and then enjoy the video.

Lo-Dash and JavaScript Performance Optimizations

http://www.youtube.com/watch?v=cD9utLH3QOk&feature=share&fb_ref=share


January 21, 2015

Douglas Crockford: Advanced JavaScript

https://www.youtube.com/watch?v=DwYPG6vreJg

January 15, 2015

Share the video I watched tonight. Good video

The Definitive Guide to Object-Oriented JavaScript

http://www.youtube.com/watch?v=PMfcsYzj-9M&feature=share&fb_ref=share

January 1, 2015

Enjoy new year day off in Vancouver. Relax, read java script definitive guide, read again and again 20 pages from 163-180, and then, learn something from the video. My new year resolution is to become a stronger java script programmer in 2015.

What the heck is the event loop anyway? JSConf EU 2014

http://www.youtube.com/attribution_link?a=Cqtja3KchL0&u=%2Fwatch%3Fv%3D8aGhZQkoFbQ%26feature%3Dshare&fb_ref=share

Dec. 30, 2015

Such a good video for me to watch, and then learn the scope chains and closures.

JavaScript Scope Chains and Closures

http://www.youtube.com/watch?v=zRZNb4GDOPI&feature=share&fb_ref=share


Dec. 27, 2015

Share the video. The CRAP rules - contrast, repeat, alignment, proximity, very great idea for website design.

HTML and CSS Web Development - Footer and Design Theory (CRAP rules) - Part 13

http://www.youtube.com/attribution_link?a=JeHOVs6tcZw&u=%2Fwatch%3Fv%3D9IpeHgl_g90%26feature%3Dshare&fb_ref=share


Dec. 14, 2014

o2 Creation Patterns Creational Patterns

https://www.youtube.com/watch?v=LjIWRvOL7aM&list=PLrzrNeNx3kNHsaPfrpPo0AlW-MhJE6gOA&index=10

Dec. 27, 2014

Make me smile, the short video, nice teaching.

HTML and CSS Web Development - How to apply transition effects - Part 14

http://www.youtube.com/watch?v=WRADgQVSWG4&feature=share&fb_ref=share

Dec. 25, 2015

My favorite half hour to watch this Java script video in Christmas day morning.

Exam Application Programming Tutorial JavaScript Quiz Online Test

http://www.youtube.com/attribution_link?a=UiB8WtJBt5A&u=%2Fwatch%3Fv%3Dd_UuOVhuCF8%26feature%3Dshare&fb_ref=share


Dec. 24, 2015

Just watch, and then, learn something interesting. Good teaching

Image Cycle JavaScript HTML CSS Web Programming Tutorial

http://www.youtube.com/watch?v=3QuSKsr47f0&feature=share&list=PL00952AC35D0A4701&index=3&fb_ref=share

Java Script Tutorial Videos  (Object oriented)

https://www.youtube.com/playlist?list=PL00952AC35D0A4701


Dec. 23, 2014

My favorite video this Christmas holiday. Java script, is a fun, challenging language to learn.

Douglas Crockford: Advanced JavaScript

http://www.youtube.com/watch?v=DwYPG6vreJg&feature=share&fb_ref=share

Dec. 21, 2014

Spent time to read the book, this weekend. Just start to read creation pattern. Good book for a programmer to start to love the java script.

Book: JavaScript Patterns

http://www.amazon.ca/JavaScript-Patterns-Stoyan-Stefanov/dp/0596806752

Dec. 15, 2014

Google I/O 2014 - Keynote

https://www.youtube.com/watch?v=wtLJPvx7-ys

Dec. 13, 2014

Such a good teaching. Excellent for a morning hour.

AngularJS Fundamentals In 60-ish Minutes

http://www.youtube.com/attribution_link?a=-U2QuDFQH48&u=%2Fwatch%3Fv%3Di9MHigUZKEM%26feature%3Dshare&fb_ref=share


http://www.youtube.com/watch?v=DwYPG6vreJg&feature=share&fb_ref=share

Dec. 13, 2015

Like the presentation. Programming can be easy with great training. Still learn java script, having fun.

Structuring JavaScript with the Revealing Module Pattern - Video

http://www.youtube.com/watch?v=V_X86VyrEjc&sns=fb

My favorite learning time is insomnia, reading does help. Learning helps more.

Using the JQuery each() Function - video

http://www.youtube.com/watch?v=Fekw8FwJcOk&sns=fb

Nov. 29, 2014

Being a big fan of the book last 2 months, motivated to rewrite the code make more readable. Coaching is such great experience, easy to read, short book, and training myself with a coach will make life much easy.

The Art of Readable Code (Theory in Practice) - Book

http://www.amazon.com/The-Readable-Code-Theory-Practice/dp/0596802293

November 29, 2014

Great video to watch, still on the way to learn Jquery, Java script.

Fundamentals for Great jQuery Development

http://www.youtube.com/watch?v=YcylSiDoOio&feature=share&fb_ref=share

Nov. 26, 2014

Share the video I watched tonight.

Douglas Crockford: The Better Parts - JSConfUY 2014

http://www.youtube.com/attribution_link?a=v2YJsPYGvZM&u=%2Fwatch%3Fv%3Dbo36MrBfTk4%26feature%3Dshare&fb_ref=share

November 17, 2014

Learning java is so much fun. Like the video.

Google I/O 2009 - Big Modular Java with Guide

http://www.youtube.com/attribution_link?a=GCVjQsKVR5E&u=%2Fwatch%3Fv%3DhBVJbzAagfs%26feature%3Dshare&fb_ref=share

Nov. 12, 2014

So many questions and answers. Like those answers.

Google I/O 2011: Programming Well with Others: Social Skills for Geeks

http://www.youtube.com/attribution_link?a=NHYbdKud8r0&u=%2Fwatch%3Fv%3Dq-7l8cnpI4k%26feature%3Dshare&fb_ref=share

Nov. 11, 2014

So many good ideas. Never thought about those ideas before. Be a manager seems to be like a teacher.

Google I/O 2010 - The joys of engineering leadership

http://www.youtube.com/attribution_link?a=7r4t5Axk4pc&u=%2Fwatch%3Fv%3DskD1fjxSRog%26feature%3Dshare&fb_ref=share

Watch the video. Two experts share principles, good points: do not burn the bridge, face time, visible/invisible work etc.

Google I/O 2012 - The Art of Organizational Manipulation

http://www.youtube.com/attribution_link?a=-05Nv51UgJU&u=%2Fwatch%3Fv%3DOTCuYzAw31Y%26feature%3Dshare&fb_ref=share


Nov. 11,2014

Videos I like

Fluent 2013: Nicholas Zakas, "A " Thank You" Can Change Your life"

http://www.youtube.com/attribution_link?a=P6SF3zGOp4U&u=%2Fwatch%3Fv%3D78eexsReL9M%26feature%3Dshare&fb_ref=share

Nov. 9, 2014

Really a struggle to read a few pages Java script definitive guide; and then, find the companion of reading, piano music, players. Learning a programming language is much easy to compare to piano.

Music video

http://www.youtube.com/attribution_link?a=pxI27DzEb5I&u=%2Fwatch%3Fv%3DAkCpX2Pnj0w%26feature%3Dshare&fb_ref=share

Nov. 2, 2014

Reading "definitive Java Script guide" is still slow, 1 hour a time, still on the page 38 out of 1098 pages. Learning a programming language needs me to be more patient.

Oct. 19, 2014

Good idea to learn a few things to write a language. It took 10 days for some one to design Java script.

JavaScript: Choose Your Own Adverture!

http://www.youtube.com/attribution_link?a=uklLhqKvXYA&u=%2Fwatch%3Fv%3D__8eIX0QFXU%26feature%3Dshare%26list%3DPLndbWGuLoHeZVgHEBjGGtCqQaXpZJfv51%26index%3D4&fb_ref=share

Learn java script programming language, warm up before I read through java script definitive guide book.

Context in JavaScript - 1/4 - Purpose and Problems with JavaScript's "This"

http://www.youtube.com/attribution_link?a=387pTjKZkJg&u=%2Fwatch%3Fv%3Dsu-SdgebJCE%26feature%3Dshare&fb_ref=share

Oct. 16, 2014

Good video to spend 1 hour.

JavaScript Essentials - video
http://www.youtube.com/attribution_link?a=9hzmx-0p57Q&u=%2Fwatch%3Fv%3D03EQu_2K2cs%26feature%3Dshare&fb_ref=share

Oct. 13, 2014

Good topic. Testable design, is a good start to think about testing.

GTAC 2010: Flexible Design? Testable Design? You Don't Have To Choose!

http://www.youtube.com/watch?v=K3q_y8H1ZTo&feature=share&fb_ref=share

Oct. 13, 2014

Watch the video, website administration work is fun and challenge sometimes.
https://www.youtube.com/watch?v=5_-YukDEDBE&list=UUtXKDgv1AVoG88PLl8nGXmw&index=427


Thanksgiving day is so much fun, and with a lot of talks and laughing and singing around the house.

Game On: 16 Design Patterns for User Engagement - Google Tech Talk

http://www.youtube.com/watch?v=YZCX-izCYMk&list=UUtXKDgv1AVoG88PLl8nGXmw&feature=share&index=21&fb_ref=share

Oct. 13, 2014

My Canadian thanksgiving morning time video - great time to relax and enjoy some talks

NYC Tech Talk Seris: Javascript Testing at Google Scale

http://www.youtube.com/watch?v=draY63DasmQ

Oct. 12, 2014

watch the video. Testability is a good topic.

Design Tech Talk Series Presents: OO Design for Testability - Google Tech Talk

http://www.youtube.com/watch?v=acjvKJiOvXw&feature=share&fb_ref=share

Oct. 11, 2014

Like this talk. Angular JS, 1 hour learning. Good time to spend at home to learn something other people working on.

Google I/O 2013 - Design Decisions in AngularJS

http://www.youtube.com/watch?v=HCR7i5F5L8c&feature=share&fb_ref=share

Like this talk. It is good for Saturday morning, organizing house while watching the video.

Google I/O 2009 - The Myth of the Genius Programmer

http://www.youtube.com/watch?v=0SARbwvhupQ&list=PLC0C39A4F2D9580F4&feature=share&fb_ref=share

Oct. 10, 2015

Learning to love Javascript. Who else is learning?

Google I/O 2011: Learning to Love JavaScript

http://www.youtube.com/attribution_link?a=mI4cQMSJT4g&u=%2Fwatch%3Fv%3DseX7jYI96GE%26feature%3Dshare&fb_ref=share

Start to watch more videos at home, learn from experts. Java script, will be my favorite language.

Speed Up Your JavaScript

http://www.youtube.com/attribution_link?a=EqQZpKBee6c&u=%2Fwatch%3Fv%3DmHtdZgou0qU%26feature%3Dshare&fb_ref=share

Oct. 7, 2014

Cannot believe that today I read this book first time. What a great book.

Functional Programming in Java

http://shop.oreilly.com/product/9781937785468.do

Oct. 5, 2014

Spent Sunday morning to watch the video. Learn Java Script language knowledge from the expert. Learning is so much fun, depth of the knowledge is out of my imagination.

Crockford on JavaScript - Chapter 2: And Then There Was JavaScript

http://www.youtube.com/attribution_link?a=AmQCwXmbO60&u=%2Fwatch%3Fv%3DRO1Wnu-xKoY%26feature%3Dshare&fb_ref=share

Oct. 2, 2014

Enjoy the talks in the evening, Model this 1+2*3, good question.

"The Clean Code Talks -- Inheritance, Polymorphism, & Testing"

https://www.youtube.com/watch?v=4F72VULWFvc

Sept. 28, 2014

Learning Java Script is so much fun. Got lost in the video first, and then, read the book to try to understand, and then, play with the sample code.

Douglas Crockford: Advanced JavaScript

http://www.youtube.com/attribution_link?a=m9mNGZ0AGLM&u=%2Fwatch%3Fv%3DDwYPG6vreJg%26feature%3Dshare&fb_ref=share

Sept. 26, 2014

So great to have a video to watch, and then, try to make sense from my own experience.

How to Write Clean, Testable Code

http://www.youtube.com/watch?v=XcT4yYu_TTs&feature=share&fb_ref=share

Sept. 25, 2014

听专家讲课, 感觉就是不一样. 原来学一个语言, 听听专家意见, 感觉如此好!

Douglas Crockford: An Inconvenient API - The Theory of the DOM

http://www.youtube.com/watch?v=Y2Y0U-2qJMs&feature=share&fb_ref=share

Like the book "testable java script"; and then, have chance to know the expert, and then, watch videos to learn Java script.

Douglas Crockford: The JavaScript Programming Language

http://www.youtube.com/attribution_link?a=6fbrVqm1kJ0&u=%2Fwatch%3Fv%3Dv2ifWcnQs6M%26feature%3Dshare&fb_ref=share

Sept. 21, 2014

So great to spend 3-4 hours in the Sunday morning to go through a book, for 30-40 pages, comparing to read all weChat blogs. Be able to read through the book and read other people's source code, really feels good.

Book: High Performance JavaScript

Leetcode 106: construct binary tree from inorder and post order traversal

Sept. 13, 2015

 Spent more than a few hours to work on the leetcode problem, and my favorite blogs about this problems:

 1. http://siddontang.gitbooks.io/leetcode-solution/content/tree/construct_binary_tree.html

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

 After reading the above reference 1, Julia spent first few hours to write the C# implementation:

 https://github.com/jianminchen/Leetcode_C-/blob/master/106ConstructuBTreeFromInorderPostOrderTraversal.cs

  In her coding practice of function build(...), she spent over 20 minutes to figure out the coding task: the code to partition the inorder traversal into two partitions, first is left subtree, second is right subtree. And then, post order traversal also can be partitioned into two intervals, first one is for left subtree, and then, second one is for right subtree.

  She took more than 10-15 minutes to understand the solution. That is too long for real problem solving. Figure out that only job is to find the root node, and then, its left child and right child is also the root node of left subtree/ or right subtree. The recursive call, actually two of them, can help to do the task.

  So, she needs to cut down the practice time, and make sure the calculation is correct, easy to tell/ maintainable code/ testable code. So, she decided to practice it using class Range instead of two arguements start/ end integers. Hopefully, this practice will enhance her memory about partition the array into two parts, one is dividing in mid point, another one is by length of first interval - left subtree.

public class Range{
public int start, end;
...

}

  Also, she likes to enhance her memory about this solution, so, she writes second implementation using C#, and see if the code can pass online judge. Most important, she tried to use different solution, to improve, challenge herself. Write the code without any mistake first time, in less than 10 minutes based on previous one.

 https://github.com/jianminchen/Leetcode_C-/blob/master/106ConstructBTreeFromInOrderPostOrderTraversal_B.cs

  Julia likes to train herself using leetcode questions, and biggest problem is to cut down the time to write a solution. She tries to cut down time from hours to 10-30 minutes.

  After the code writing, she thought about more about great ideas out there, she should not miss. So, she reads the second reference, and like the most about the analysis:
"这道题和Construct Binary Tree from Preorder and Inorder Traversal是树中难度比较大的题目了，有朋友可能会想根据先序遍历和后序遍历能不能重新构造出树来，答案是否定的。只有中序便利可以根据根的位置切开左右子树，其他两种遍历都不能做到，其实先序遍历和后序遍历是不能唯一确定一棵树的，会有歧义发生，也就是两棵不同的树可以有相同的先序遍历和后序遍历，有兴趣的朋友可以试试举出这种例子."

  Julia 发现在训练自己做题是, 如果能摸索出方法, 提高写代码的速度, 从几个小时, 到10-30 分钟, 那就是很成功的训练. 一种方式, 就是, 找到她喜欢的题解, 能够理解算法; 接下来, 看如何提高写代码的速度, 最好的方式, 就是多写几个解法, 看哪个不容易出错. 

 最后, 就是, 快速看十几个博客, 看有没有错过最重要, 最关键的分析. 

 接下来, 就是重复训练; 分析超时的原因, 能不能达到目的10-15分钟写出正确的代码. 就像网球训练, 训练自己. 

Backtracking algorithm: rat in maze

Sept. 10, 2015

  Study again the back tracking algorithm using recursive solution, rat in maze, a classical problem. Made a few of mistakes through the practice, one is how to use two dimension array, another one is that "not all return path returns value", not so confident that "return false" at the end of function.

  重温二年前做过的算法题, Rat in Maze, 为自己惭愧! 二年前的练习, 没有任何的参考网页信息, 也没有算法讨论, 尝试改进. 感觉到自己的差距, 这次练习, 着重强调把算法能背出来. 一步一步写出来, 发现几个错误. 二维数组不熟悉, 耽误了十几分钟; 另外, 就是, "return false" 在递归函数最后一句, 先是忘了. 总之, 这个经典题目, 十分钟写不出来; 需要二个数组, 边界条件检测, 一点印象没有.

  Here are my favorite blogs about this problem:

1. http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/

2. http://algorithms.tutorialhorizon.com/backtracking-rat-in-a-maze-puzzle/

3. https://www.cs.bu.edu/teaching/alg/maze/


  Julia's C# pratice:

  https://github.com/jianminchen/AlgorithmsPractice/blob/master/RatInAMaze_BackTracking.cs

  And then, try to find more discussion about this problem, came cross blogs to challenge my analysis skills. 搜一下Google, 找到一个很有深度的网页, 看了以后, 体验一下代码, 感觉比自己的水平高了几个档次.

  http://blogs.msdn.com/b/mattwar/archive/2005/02/03/366498.aspx

  http://blogs.msdn.com/b/mattwar/archive/2005/02/11/371274.aspx

  More code to read and then play:

http://www.evercrest.com/ext/CheeseAppropriator.cs

  and C# practice:

https://github.com/jianminchen/AlgorithmsPractice/blob/master/MousingAround.cs

January 10, 2016
Review the algorithm

Follow up 

April 27, 2017

Draw a circle algorithm

August 18, 2015

Interesting problem – draw a circle,

blogs to read:

1. http://petercai.com/the-microsoft-sde-interview/

2. http://www.startuplessonslearned.com/2008/11/abcdefs-of-conducting-technical.html

3. https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

C# code I wrote in Dec. 2012 is here. 

Follow up 

January 23, 2018

I traced my outlook email and then I found out that it is one of my phone screen algorithm I got in 2012. I supposed to write in 20 - 30 minutes, and at most 40 - 50 minutes.  

"More detail about the draw circle program, in first 10 minutes, I came out a mediocre solution, an then I tried to catch up while coding to put more ideas in, so I changed the original idea to set a target, and then made this 1000 tries to reach the target; the algorithm is like an undetermined optimal algorithm, with a lot of mistakes, losing the focus sometimes. I should have clarified the requirements with you before I started yesterday and work in the right direction. "

It is such a great feeling to read what I wrote in 2012. It is more than 6 years ago. At that time, I was too shy and I did not have habit to write daily. And I still remembered that I was so excited to have a phone screen, at that time, as a software developer, I was too isolated and my personality was kind of introvert. I was afraid to write down what I think at that time.

C# code I wrote in Dec. 2012 is here. Read the code I wrote more than 6 years ago. How to define the feeling? It is like meeting an old friend, sweet and sour. But this time the sour is mild level, code smells make the sour feeling. 

Code review and then C# code is written, the link is here. 

Morris post order traversal algorithm

Sept. 5, 2015

花时间把代码读明白, 比光看书强. 动手写代码, 改代码,  
兴趣是最好的老师. 多记几个例子, 增加情趣. 

举个例子关于中序遍历, 

           4

        /     \

       2       6

     /  \     / \

    1   3   5   7 

easy way to travel is to remember the order of its position in the horizontal way 

       

现在, 要做Morris 的后序遍历, 有一个技巧, 是在我写完这个C#代码才发现的, 

                     

9                 /    \

5      8

/ \       \

1   4     7

/ \   /

2   3 6 就是从最左边开始, 遍历五次,   1,   2,   3, 4, 5   6,   7, 8, 9,  最后结果是 1 2 3 4 5 6 7 8 9  加一个dummy node, with left child is the root node.

Morris post order traversal

blogs to read:
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html


C# implementation:
https://github.com/jianminchen/MorrisOrder/blob/master/MorrisPostOrder.cs


Morris order in order traversal

https://github.com/jianminchen/MorrisInOrderTraverse/blob/master/Program.cs