本文主要解決一個問題移剪，如何實現(xiàn)二叉樹的前中后序遍歷究珊，有兩個要求：
- O(1)空間復(fù)雜度，即只能使用常數(shù)空間纵苛；
- 二叉樹的形狀不能被破壞（中間過程允許改變其形狀）剿涮。
通常，實現(xiàn)二叉樹的前序（preorder）攻人、中序（inorder）取试、后序（postorder）遍歷有兩個常用的方法：一是遞歸(recursive)，二是使用棧實現(xiàn)的迭代版本(stack+iterative)怀吻。這兩種方法都是O(n)的空間復(fù)雜度（遞歸本身占用stack空間或者用戶自定義的stack）瞬浓，所以不滿足要求。
Morris Traversal方法可以做到這兩點烙博，與前兩種方法的不同在于該方法只需要O(1)空間瑟蜈，而且同樣可以在O(n)時間內(nèi)完成烟逊。
要使用O(1)空間進(jìn)行遍歷，最大的難點在于铺根，遍歷到子節(jié)點的時候怎樣重新返回到父節(jié)點（假設(shè)節(jié)點中沒有指向父節(jié)點的p指針）宪躯，由于不能用棧作為輔助空間。為了解決這個問題位迂，Morris方法用到了線索二叉樹（threaded binary tree）的概念访雪。在Morris方法中不需要為每個節(jié)點額外分配指針指向其前驅(qū)（predecessor）和后繼節(jié)點（successor），只需要利用葉子節(jié)點中的左右空指針指向某種順序遍歷下的前驅(qū)節(jié)點或后繼節(jié)點就可以了掂林。
Morris只提供了中序遍歷的方法臣缀，在中序遍歷的基礎(chǔ)上稍加修改可以實現(xiàn)前序，而后續(xù)就要再費點心思了泻帮。所以先從中序開始介紹精置。
首先定義在這篇文章中使用的二叉樹節(jié)點結(jié)構(gòu)，即由val锣杂，left和right組成：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
一脂倦、中序遍歷
步驟：
如果當(dāng)前節(jié)點的左孩子為空，則輸出當(dāng)前節(jié)點并將其右孩子作為當(dāng)前節(jié)點元莫。
-
如果當(dāng)前節(jié)點的左孩子不為空赖阻，在當(dāng)前節(jié)點的左子樹中找到當(dāng)前節(jié)點在中序遍歷下的前驅(qū)節(jié)點。
a) 如果前驅(qū)節(jié)點的右孩子為空踱蠢，將它的右孩子設(shè)置為當(dāng)前節(jié)點火欧。當(dāng)前節(jié)點更新為當(dāng)前節(jié)點的左孩子。
b) 如果前驅(qū)節(jié)點的右孩子為當(dāng)前節(jié)點茎截，將它的右孩子重新設(shè)為空（恢復(fù)樹的形狀）苇侵。輸出當(dāng)前節(jié)點。當(dāng)前節(jié)點更新為當(dāng)前節(jié)點的右孩子稼虎。
重復(fù)以上1衅檀、2直到當(dāng)前節(jié)點為空。
圖示：
下圖為每一步迭代的結(jié)果（從左至右霎俩，從上到下），cur代表當(dāng)前節(jié)點沉眶，深色節(jié)點表示該節(jié)點已輸出打却。
代碼:
void inorderMorrisTraversal(TreeNode *root) {
TreeNode *cur = root, *prev = NULL;
while (cur != NULL)
{
if (cur->left == NULL) // 1.
{
printf("%d ", cur->val);
cur = cur->right;
}
else
{
// find predecessor
prev = cur->left;
while (prev->right != NULL && prev->right != cur)
prev = prev->right;
if (prev->right == NULL) // 2.a)
{
prev->right = cur;
cur = cur->left;
}
else // 2.b)
{
prev->right = NULL;
printf("%d ", cur->val);
cur = cur->right;
}
}
}
}
復(fù)雜度分析：
空間復(fù)雜度：O(1)，因為只用了兩個輔助指針谎倔。
時間復(fù)雜度：O(n)柳击。證明時間復(fù)雜度為O(n)，最大的疑惑在于尋找中序遍歷下二叉樹中所有節(jié)點的前驅(qū)節(jié)點的時間復(fù)雜度是多少片习，即以下兩行代碼：
while (prev->right != NULL && prev->right != cur)
prev = prev->right;
直覺上捌肴，認(rèn)為它的復(fù)雜度是O(nlgn)蹬叭，因為找單個節(jié)點的前驅(qū)節(jié)點與樹的高度有關(guān)。但事實上状知，尋找所有節(jié)點的前驅(qū)節(jié)點只需要O(n)時間秽五。n個節(jié)點的二叉樹中一共有n-1條邊，整個過程中每條邊最多只走2次饥悴，一次是為了定位到某個節(jié)點坦喘，另一次是為了尋找上面某個節(jié)點的前驅(qū)節(jié)點，如下圖所示西设，其中紅色是為了定位到某個節(jié)點瓣铣，黑色線是為了找到前驅(qū)節(jié)點。所以復(fù)雜度為O(n)贷揽。
二棠笑、前序遍歷
前序遍歷與中序遍歷相似，代碼上只有一行不同禽绪，不同就在于輸出的順序腐晾。
步驟：
如果當(dāng)前節(jié)點的左孩子為空，則輸出當(dāng)前節(jié)點并將其右孩子作為當(dāng)前節(jié)點丐一。
-
如果當(dāng)前節(jié)點的左孩子不為空藻糖，在當(dāng)前節(jié)點的左子樹中找到當(dāng)前節(jié)點在中序遍歷下的前驅(qū)節(jié)點。
a) 如果前驅(qū)節(jié)點的右孩子為空库车，將它的右孩子設(shè)置為當(dāng)前節(jié)點巨柒。輸出當(dāng)前節(jié)點（在這里輸出，這是與中序遍歷唯一一點不同）柠衍。當(dāng)前節(jié)點更新為當(dāng)前節(jié)點的左孩子洋满。
b) 如果前驅(qū)節(jié)點的右孩子為當(dāng)前節(jié)點，將它的右孩子重新設(shè)為空珍坊。當(dāng)前節(jié)點更新為當(dāng)前節(jié)點的右孩子牺勾。
重復(fù)以上1泌辫、2直到當(dāng)前節(jié)點為空纫普。
圖示：
代碼
void preorderMorrisTraversal(TreeNode *root) {
TreeNode *cur = root, *prev = NULL;
while (cur != NULL)
{
if (cur->left == NULL)
{
printf("%d ", cur->val);
cur = cur->right;
}
else
{
prev = cur->left;
while (prev->right != NULL && prev->right != cur)
prev = prev->right;
if (prev->right == NULL)
{
printf("%d ", cur->val); // the only difference with inorder-traversal
prev->right = cur;
cur = cur->left;
}
else
{
prev->right = NULL;
cur = cur->right;
}
}
}
}
復(fù)雜度分析：
時間復(fù)雜度與空間復(fù)雜度都與中序遍歷時的情況相同。
三悼嫉、后序遍歷
后續(xù)遍歷稍顯復(fù)雜履怯，需要建立一個臨時節(jié)點dump回还，令其左孩子是root。并且還需要一個子過程叹洲，就是倒序輸出某兩個節(jié)點之間路徑上的各個節(jié)點柠硕。
步驟：
當(dāng)前節(jié)點設(shè)置為臨時節(jié)點dump。
如果當(dāng)前節(jié)點的左孩子為空运提，則將其右孩子作為當(dāng)前節(jié)點蝗柔。
-
如果當(dāng)前節(jié)點的左孩子不為空闻葵，在當(dāng)前節(jié)點的左子樹中找到當(dāng)前節(jié)點在中序遍歷下的前驅(qū)節(jié)點。
a) 如果前驅(qū)節(jié)點的右孩子為空癣丧，將它的右孩子設(shè)置為當(dāng)前節(jié)點槽畔。當(dāng)前節(jié)點更新為當(dāng)前節(jié)點的左孩子。
b) 如果前驅(qū)節(jié)點的右孩子為當(dāng)前節(jié)點坎缭，將它的右孩子重新設(shè)為空竟痰。倒序輸出從當(dāng)前節(jié)點的左孩子到該前驅(qū)節(jié)點這條路徑上的所有節(jié)點。當(dāng)前節(jié)點更新為當(dāng)前節(jié)點的右孩子掏呼。
重復(fù)以上1坏快、2直到當(dāng)前節(jié)點為空。
圖示：
代碼:
void reverse(TreeNode *from, TreeNode *to) // reverse the tree nodes 'from' -> 'to'.
{
if (from == to)
return;
TreeNode *x = from, *y = from->right, *z;
while (true)
{
z = y->right;
y->right = x;
x = y;
y = z;
if (x == to)
break;
}
}
void printReverse(TreeNode* from, TreeNode *to) // print the reversed tree nodes 'from' -> 'to'.
{
reverse(from, to);
TreeNode *p = to;
while (true)
{
printf("%d ", p->val);
if (p == from)
break;
p = p->right;
}
reverse(to, from);
}
void postorderMorrisTraversal(TreeNode *root) {
TreeNode dump(0);
dump.left = root;
TreeNode *cur = &dump, *prev = NULL;
while (cur)
{
if (cur->left == NULL)
{
cur = cur->right;
}
else
{
prev = cur->left;
while (prev->right != NULL && prev->right != cur)
prev = prev->right;
if (prev->right == NULL)
{
prev->right = cur;
cur = cur->left;
}
else
{
printReverse(cur->left, prev); // call print
prev->right = NULL;
cur = cur->right;
}
}
}
}
復(fù)雜度分析：
空間復(fù)雜度同樣是O(1)憎夷；時間復(fù)雜度也是O(n)莽鸿，倒序輸出過程只不過是加大了常數(shù)系數(shù)。
參考：
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
http://www.geeksforgeeks.org/morris-traversal-for-preorder/
http://stackoverflow.com/questions/6478063/how-is-the-complexity-of-morris-traversal-on
http://blog.csdn.net/wdq347/article/details/8853371
Data Structures and Algorithms in C++ by Adam Drozdek
本文轉(zhuǎn)自Morris Traversal方法遍歷二叉樹（非遞歸拾给，不用棧祥得，O(1)空間）
