http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html

Inorder:

``````1 void inorderMorrisTraversal(TreeNode *root) {
2     TreeNode *cur = root, *prev = NULL;
3     while (cur != NULL)
4     {
5         if (cur->left == NULL)          // 1.
6         {
7             printf("%d ", cur->val);
8             cur = cur->right;
9         }
10         else
11         {
12             // find predecessor
13             prev = cur->left;
14             while (prev->right != NULL && prev->right != cur)
15                 prev = prev->right;
16
17             if (prev->right == NULL)   // 2.a)
18             {
19                 prev->right = cur;
20                 cur = cur->left;
21             }
22             else                       // 2.b)
23             {
24                 prev->right = NULL;
25                 printf("%d ", cur->val);
26                 cur = cur->right;
27             }
28         }
29     }
30 }
``````

Preorder:

`````` 1 void preorderMorrisTraversal(TreeNode *root) {
2     TreeNode *cur = root, *prev = NULL;
3     while (cur != NULL)
4     {
5         if (cur->left == NULL)
6         {
7             printf("%d ", cur->val);
8             cur = cur->right;
9         }
10         else
11         {
12             prev = cur->left;
13             while (prev->right != NULL && prev->right != cur)
14                 prev = prev->right;
15
16             if (prev->right == NULL)
17             {
18                 printf("%d ", cur->val);  // the only difference with inorder-traversal
19                 prev->right = cur;
20                 cur = cur->left;
21             }
22             else
23             {
24                 prev->right = NULL;
25                 cur = cur->right;
26             }
27         }
28     }
29 }
``````

`````` 1 void reverse(TreeNode *from, TreeNode *to) // reverse the tree nodes 'from' -> 'to'.
2 {
3     if (from == to)
4         return;
5     TreeNode *x = from, *y = from->right, *z;
6     while (true)
7     {
8         z = y->right;
9         y->right = x;
10         x = y;
11         y = z;
12         if (x == to)
13             break;
14     }
15 }
16
17 void printReverse(TreeNode* from, TreeNode *to) // print the reversed tree nodes 'from' -> 'to'.
18 {
19     reverse(from, to);
20
21     TreeNode *p = to;
22     while (true)
23     {
24         printf("%d ", p->val);
25         if (p == from)
26             break;
27         p = p->right;
28     }
29
30     reverse(to, from);
31 }
32
33 void postorderMorrisTraversal(TreeNode *root) {
34     TreeNode dump(0);
35     dump.left = root;
36     TreeNode *cur = &dump, *prev = NULL;
37     while (cur)
38     {
39         if (cur->left == NULL)
40         {
41             cur = cur->right;
42         }
43         else
44         {
45             prev = cur->left;
46             while (prev->right != NULL && prev->right != cur)
47                 prev = prev->right;
48
49             if (prev->right == NULL)
50             {
51                 prev->right = cur;
52                 cur = cur->left;
53             }
54             else
55             {
56                 printReverse(cur->left, prev);  // call print
57                 prev->right = NULL;
58                 cur = cur->right;
59             }
60         }
61     }
62 }
``````