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

Leetcode: Recover binary search tree

August 31, 2015

   想写点什么, 因为这道题花了我好几个小时, 在周日, 除了在球场上跑了二个小时, 就泡在这道题上面.

read blogs: http://www.lifeincode.net/programming/leetcode-recover-binary-search-tree-java/ http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html C# implementations: 没有明白算法, 写了一个C#版本, 从读代码, 看有哪些不明白的地方. https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoverBinarySearchTree.cs 简易递归版本, 但是, 找二个违例点不是很到位.  https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoverBinarySearchTreeB.cs 总算明白, 开始写几个小函数, 看能不能记住, 容易维护, 测试案例是不是很清楚. 比较满意的代码. 看看注释, 几个月过后, 希望能几分钟内回忆起算法.  明白了算法, 再把代码写清楚, 让错误无处可藏. work on extracting small functions, and then, understand the algorithm better. No place for a bug.  https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoveryBinarySearchTree_C.cs 有空周末在黑板上讲讲这道题, 练习自己的表达能力, 做一个小录像, 放在网上.

Leetcode Question No 70: climbing stairs

July 28, 2015

Problem statement:

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

The problem is most popular question in the algorithm, so I do like to spend time to find out all sorts of solution, and get myself comfortable to all kinds of ideas, and figure out which one is best, and all concerns we can have in the discussion of climbing stairs:

1. Recursion solution vs. DP problem solution (Dynamic Programming solution)

2. Time complexity solution: O(2^n) vs O(n) solution

3. The space O(N) vs O(1), in other words: array of N or 2 variable, and another tmp variable

4. The base case discussion: f(0) = 1 or f(0) =1, math question?

5. Math formula - closed form solution vs DP problem solution
6. Use Memoization DP vs. no memoization DP
7. Programming skills, how to make code easy to follow, more readable, more abstract. 

The investment of time on the problem is well done. Go over 16 implementation one by one using C# programming language. 

C# code:

https://github.com/jianminchen/climbingStairs/blob/master/climbingStairs.cs

其实, 我觉得题目越容易, 越值得投入时间去学习; 看看大家有没有不同的理解, 打开思路; 如果自己没有训练过这道题, 可能会紧张; 即使训练过, 但是, 有的想法, 可能自己从来没有思考过, 一时还不能判断好坏, 但是, 多看网上的博客, 向每一个人取取经. 谦虚, 才能有提高.

我编网站后台, C#程序自己写; 自己训练的题目太少; 这次选择用Leetcode来提高C#编程, 又可以提高算法和数据结构的知识, 网站后台靠平时训练.  

January 3, 2016

Review the leetcode question 70, climbing stairs. 

Read the blog:

http://blog.csdn.net/kenden23/article/details/17377869
http://yucoding.blogspot.ca/2012/12/leetcode-question-15-climbing-stairs.html

http://www.cnblogs.com/springfor/p/3886576.html

http://www.cnblogs.com/springfor/p/3886576.html

http://siddontang.gitbooks.io/leetcode-solution/content/dynamic_programming/climbing_stairs.html

https://github.com/zwxxx/LeetCode/blob/master/Climbing_Stairs.cpp