Binary Tree Inorder traversal - Iterative solution - warm up practice

May 25, 2016 Review binary tree inorder iterative solution, add some test cases. Julia C# practice code of binary tree C# practice Questions and Answers: 1. How is the practice of inorder traversal iterative solution? Julia compared to the other solution, line 354 - line 372, inOrderIterative_B https://github.com/jianminchen/leetcode-tree/blob/master/TreeDemo.cs and chose this one to practice: C# practice She wrote some comment to argue that the solution is very efficient and no redundant code. She likes to use reasoning and analysis to help her structure the function. Here are her analysis:           1. First, argue that line 88, why to check "if stack is empty, break the while loop" before outputting any node in the stack. Otherwise, if the stack is empty, then, line 91: execution run time error. 2. Second, argue that output of inorder traversal nodes is not in inner loop. If there are more than 1 in a row to output, then the outer while loop (line 79) will take care of it.       3. Third, argue that line 94: runner = runner.right; It does not matter that right child exists or not, line 81 will take care of null.  Complete one iteration - Push nodes into stack, then first node in inorder is on the top of stack, If stack is empty, break; otherwise, ready to pop top one from the stack, and then, move runner to its right child. Follow up after 12 months March 27, 2017 Read the blog and think about the better presentation, more readable.  Write another C# practice, and post a question about binary tree inorder traversal (iterative solution) for code review.

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分钟写出正确的代码. 就像网球训练, 训练自己.