本文主要解決一個(gè)問(wèn)題，如何實(shí)現(xiàn)二叉樹(shù)的前中后序遍歷，有兩個(gè)要求：
- O(1)空間復(fù)雜度，即只能使用常數(shù)空間；
- 二叉樹(shù)的形狀不能被破壞（中間過(guò)程允許改變其形狀）。
通常，實(shí)現(xiàn)二叉樹(shù)的前序（preorder）、中序（inorder）、后序（postorder）遍歷有兩個(gè)常用的方法：一是遞歸(recursive)，二是使用棧實(shí)現(xiàn)的迭代版本(stack+iterative)。這兩種方法都是O(n)的空間復(fù)雜度（遞歸本身占用stack空間或者用戶自定義的stack），所以不滿足要求。
Morris Traversal方法可以做到這兩點(diǎn)，與前兩種方法的不同在于該方法只需要O(1)空間，而且同樣可以在O(n)時(shí)間內(nèi)完成。
要使用O(1)空間進(jìn)行遍歷，最大的難點(diǎn)在于，遍歷到子節(jié)點(diǎn)的時(shí)候怎樣重新返回到父節(jié)點(diǎn)（假設(shè)節(jié)點(diǎn)中沒(méi)有指向父節(jié)點(diǎn)的p指針），由于不能用棧作為輔助空間。為了解決這個(gè)問(wèn)題，Morris方法用到了線索二叉樹(shù)（threaded binary tree）的概念。在Morris方法中不需要為每個(gè)節(jié)點(diǎn)額外分配指針指向其前驅(qū)（predecessor）和后繼節(jié)點(diǎn)（successor），只需要利用葉子節(jié)點(diǎn)中的左右空指針指向某種順序遍歷下的前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn)就可以了。
Morris只提供了中序遍歷的方法，在中序遍歷的基礎(chǔ)上稍加修改可以實(shí)現(xiàn)前序，而后續(xù)就要再費(fèi)點(diǎn)心思了。所以先從中序開(kāi)始介紹。
首先定義在這篇文章中使用的二叉樹(shù)節(jié)點(diǎn)結(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é)點(diǎn)的左孩子為空，則輸出當(dāng)前節(jié)點(diǎn)并將其右孩子作為當(dāng)前節(jié)點(diǎn)。
-
如果當(dāng)前節(jié)點(diǎn)的左孩子不為空，在當(dāng)前節(jié)點(diǎn)的左子樹(shù)中找到當(dāng)前節(jié)點(diǎn)在中序遍歷下的前驅(qū)節(jié)點(diǎn)。
a) 如果前驅(qū)節(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前節(jié)點(diǎn)。當(dāng)前節(jié)點(diǎn)更新為當(dāng)前節(jié)點(diǎn)的左孩子。
b) 如果前驅(qū)節(jié)點(diǎn)的右孩子為當(dāng)前節(jié)點(diǎn)，將它的右孩子重新設(shè)為空（恢復(fù)樹(shù)的形狀）。輸出當(dāng)前節(jié)點(diǎn)。當(dāng)前節(jié)點(diǎn)更新為當(dāng)前節(jié)點(diǎn)的右孩子。
重復(fù)以上1、2直到當(dāng)前節(jié)點(diǎn)為空。
圖示：
下圖為每一步迭代的結(jié)果（從左至右，從上到下），cur代表當(dāng)前節(jié)點(diǎn)，深色節(jié)點(diǎn)表示該節(jié)點(diǎn)已輸出。
代碼:
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)，因?yàn)橹挥昧藘蓚€(gè)輔助指針。
時(shí)間復(fù)雜度：O(n)。證明時(shí)間復(fù)雜度為O(n)，最大的疑惑在于尋找中序遍歷下二叉樹(shù)中所有節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的時(shí)間復(fù)雜度是多少，即以下兩行代碼：
while (prev->right != NULL && prev->right != cur)
prev = prev->right;
直覺(jué)上，認(rèn)為它的復(fù)雜度是O(nlgn)，因?yàn)檎覇蝹€(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)與樹(shù)的高度有關(guān)。但事實(shí)上，尋找所有節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)只需要O(n)時(shí)間。n個(gè)節(jié)點(diǎn)的二叉樹(shù)中一共有n-1條邊，整個(gè)過(guò)程中每條邊最多只走2次，一次是為了定位到某個(gè)節(jié)點(diǎn)，另一次是為了尋找上面某個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，如下圖所示，其中紅色是為了定位到某個(gè)節(jié)點(diǎn)，黑色線是為了找到前驅(qū)節(jié)點(diǎn)。所以復(fù)雜度為O(n)。
二、前序遍歷
前序遍歷與中序遍歷相似，代碼上只有一行不同，不同就在于輸出的順序。
步驟：
如果當(dāng)前節(jié)點(diǎn)的左孩子為空，則輸出當(dāng)前節(jié)點(diǎn)并將其右孩子作為當(dāng)前節(jié)點(diǎn)。
-
如果當(dāng)前節(jié)點(diǎn)的左孩子不為空，在當(dāng)前節(jié)點(diǎn)的左子樹(shù)中找到當(dāng)前節(jié)點(diǎn)在中序遍歷下的前驅(qū)節(jié)點(diǎn)。
a) 如果前驅(qū)節(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前節(jié)點(diǎn)。輸出當(dāng)前節(jié)點(diǎn)（在這里輸出，這是與中序遍歷唯一一點(diǎn)不同）。當(dāng)前節(jié)點(diǎn)更新為當(dāng)前節(jié)點(diǎn)的左孩子。
b) 如果前驅(qū)節(jié)點(diǎn)的右孩子為當(dāng)前節(jié)點(diǎn)，將它的右孩子重新設(shè)為空。當(dāng)前節(jié)點(diǎn)更新為當(dāng)前節(jié)點(diǎn)的右孩子。
重復(fù)以上1、2直到當(dāng)前節(jié)點(diǎn)為空。
圖示：
代碼
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ù)雜度分析：
時(shí)間復(fù)雜度與空間復(fù)雜度都與中序遍歷時(shí)的情況相同。
三、后序遍歷
后續(xù)遍歷稍顯復(fù)雜，需要建立一個(gè)臨時(shí)節(jié)點(diǎn)dump，令其左孩子是root。并且還需要一個(gè)子過(guò)程，就是倒序輸出某兩個(gè)節(jié)點(diǎn)之間路徑上的各個(gè)節(jié)點(diǎn)。
步驟：
當(dāng)前節(jié)點(diǎn)設(shè)置為臨時(shí)節(jié)點(diǎn)dump。
如果當(dāng)前節(jié)點(diǎn)的左孩子為空，則將其右孩子作為當(dāng)前節(jié)點(diǎn)。
-
如果當(dāng)前節(jié)點(diǎn)的左孩子不為空，在當(dāng)前節(jié)點(diǎn)的左子樹(shù)中找到當(dāng)前節(jié)點(diǎn)在中序遍歷下的前驅(qū)節(jié)點(diǎn)。
a) 如果前驅(qū)節(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前節(jié)點(diǎn)。當(dāng)前節(jié)點(diǎn)更新為當(dāng)前節(jié)點(diǎn)的左孩子。
b) 如果前驅(qū)節(jié)點(diǎn)的右孩子為當(dāng)前節(jié)點(diǎn)，將它的右孩子重新設(shè)為空。倒序輸出從當(dāng)前節(jié)點(diǎn)的左孩子到該前驅(qū)節(jié)點(diǎn)這條路徑上的所有節(jié)點(diǎn)。當(dāng)前節(jié)點(diǎn)更新為當(dāng)前節(jié)點(diǎn)的右孩子。
重復(fù)以上1、2直到當(dāng)前節(jié)點(diǎn)為空。
圖示：
代碼:
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)；時(shí)間復(fù)雜度也是O(n)，倒序輸出過(guò)程只不過(guò)是加大了常數(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方法遍歷二叉樹(shù)（非遞歸，不用棧，O(1)空間）
