Sunday, September 6, 2015

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.  


No comments:

Post a Comment