Morris Traversal
- 非遞歸，不用棧，空間O(1)時(shí)間O(n)
- 二叉樹的形狀不能被破壞（中間過程允許改變形狀）
- Morris Traveral只提供了中序遍歷的算法，在中序遍歷的基礎(chǔ)上稍加修改可以實(shí)現(xiàn)前序，而后續(xù)就要再費(fèi)點(diǎn)心思了。
二叉樹結(jié)構(gòu)：
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)的左子樹中找到當(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ù)樹的形狀）。輸出當(dāng)前節(jié)點(diǎn)。當(dāng)前節(jié)點(diǎn)更新為當(dāng)前節(jié)點(diǎn)的右孩子。
重復(fù)以上1、2直到當(dāng)前節(jié)點(diǎn)為空。
例如二叉樹：
4
/ \
2 6
/ \ / \
1 3 5 7
尋找前驅(qū)的過程中：
節(jié)點(diǎn) 3 的右孩子應(yīng)該指向節(jié)點(diǎn) 4；
節(jié)點(diǎn) 1 的右孩子應(yīng)該指向節(jié)點(diǎn) 2；
節(jié)點(diǎn) 5 的右孩子應(yīng)該指向節(jié)點(diǎn) 6；
在第二次訪問的時(shí)候以上前驅(qū)的右孩子重新被置為NULL；
圖示：
下圖為每一步迭代的結(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
{
// 尋找cur的前驅(qū)（指向其的線索）
prev = cur->left;
while (prev->right != NULL && prev->right != cur)
prev = prev->right;
if (prev->right == NULL) // 2.a)
{
prev->right = cur; //設(shè)置右孩子線索
cur = cur->left;
}
else // 2.b)
{
prev->right = NULL; //線索用過了，重設(shè)
printf("%d ", cur->val);
cur = cur->right;
}
}
}
}
復(fù)雜度分析：
空間復(fù)雜度：O(1)，因?yàn)橹挥昧藘蓚€(gè)輔助指針。
時(shí)間復(fù)雜度：O(n)。證明時(shí)間復(fù)雜度為O(n)，最大的疑惑在于尋找中序遍歷下二叉樹中所有節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的時(shí)間復(fù)雜度是多少，即以下兩行代碼：
while (prev->right != NULL && prev->right != cur)
prev = prev->right;
直覺上，認(rèn)為它的復(fù)雜度是O(nlgn)，因?yàn)檎覇蝹€(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)與樹的高度有關(guān)。但事實(shí)上，尋找所有節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)只需要O(n)時(shí)間。n個(gè)節(jié)點(diǎn)的二叉樹中一共有n-1條邊，整個(gè)過程中每條邊最多只走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)的左子樹中找到當(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ù)遍歷
后續(xù)遍歷稍顯復(fù)雜，需要建立一個(gè)臨時(shí)節(jié)點(diǎn)dump，令其左孩子是root。并且還需要一個(gè)子過程，就是倒序輸出某兩個(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)的左子樹中找到當(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)，倒序輸出過程只不過是加大了常數(shù)系數(shù)。
鳴謝與參考：
? AnnieKim
遞歸
代碼：
中序遍歷（前序、后序遍歷可以在此基礎(chǔ)上更改）
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> nodes;
inorder(root, nodes);
return nodes;
}
private:
void inorder(TreeNode* root, vector<int>& nodes) {
if (!root) {
return;
}
inorder(root -> left, nodes);
nodes.push_back(root -> val);
inorder(root -> right, nodes);
}
};
迭代（棧+迭代）
代碼
中序遍歷（前序、后序遍歷可以在此基礎(chǔ)上更改）
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> nodes;
stack<TreeNode*> todo;
while (root || !todo.empty()) {
while (root) {
todo.push(root);
root = root -> left;
}
root = todo.top();
todo.pop();
nodes.push_back(root -> val);
root = root -> right;
}
return nodes;
}
};
