[LeetCode] Flatten Binary Tree to Linked List

时间：2015-06-03 00:39:17 收藏：0 阅读：190

This problem seems to be tricky at first glance. However, if you know Morris traversal, it is just the preorder case of Morris traversal and the code is really short.

 1     void flatten(TreeNode* root) {
 2         TreeNode* curNode = root;
 3         while (curNode) {
 4             if (curNode -> left) {
 5                 TreeNode* predecessor = curNode -> left;
 6                 while (predecessor -> right)
 7                     predecessor = predecessor -> right;
 8                 predecessor -> right = curNode -> right;
 9                 curNode -> right = curNode -> left;
10                 curNode -> left = NULL;
11             }
12             else curNode = curNode -> right;
13         }
14     }

For more about Morris traversal, please visit these solutions: morris-preorder, morris-inorder, morris-postorder.

原文：http://www.cnblogs.com/jcliBlogger/p/4548070.html