莫里斯演算法與線索二叉樹有異曲同工之妙，建議先了解線索二叉樹，再來學習
Morris演算法
- 莫里斯演算法思想
- 前序遍歷
- 中序遍歷
- 后序遍歷
莫里斯演算法思想
- mirror遍歷用到了線索二叉樹的思想,在Morris方法中不需要為每個節點額外分配指標指向其前(predecessor）和后繼節點（successor）,只需要利用葉子節點中的左右空指標指向某種順序遍歷下的前驅節點或后繼節點就可以了 ，
Morris的整體思路就是將 以某個根結點開始，找到它左子樹的最右側節點之后與這個根結點進行連接
我們可以從 圖2 看到，如果這么連接之后，cur 這個指標是可以完整的從一個節點順著下一個節點遍歷，將整棵樹遍歷完畢，直到 7 這個節點右側沒有指向，
代碼整體模板演示: - 如果可以建議大家反復對照上圖與代碼，和我給出關于自己的詳細思考，好好想想，
- 我盡可能做到對每條代碼都做出詳細解釋
class Solution {
public:
void preOrderMorris(TreeNode* root) {
if (root == NULL)
return;
TreeNode* curr = root; // 當前的結點
TreeNode* currLeft = NULL; // 當前結點的左子樹
while (curr != NULL)
{
currLeft = curr->left;
// 當前結點的左子樹存在即可建立連接
if (currLeft != NULL)
{
// 找到當前左子樹的最右側節點，并且不能沿著連接回傳上層
while (currLeft->right != NULL && currLeft->right != curr)
currLeft = currLeft->right;
//最右側節點的右指標沒有指向根結點，創建連接并往下一個左子樹的根結點進行連接操作
if (currLeft->right == NULL)
{
currLeft->right = curr;
curr = curr.left;
continue; // 這個continue很關鍵
}
else
//當左子樹的最右側節點有指向根結點，此時說明我們已經進入到了回傳上層的階段，不再是一開始的建立連接階段，同時在回到根結點時我們應已處理完下層節點，直接斷開連接即可，
currLeft->right = NULL;
}
// 回傳上層的階段不斷向右走
curr = curr.right;
}
}
}
- 上面的代碼和解釋可能看完后依舊糊涂，沒關系，下面我通過圖來演示cur1和cur2指標移動的程序:
- 到此為止，左子樹部分就已經處理完畢了，下面右子樹
總結:
- 連接程序:先連接后左移
- 復原程序：先右移后斬斷，若斬斷位置到位，立刻執行斬斷，如果位置不到位，通過while回圈到達指定位置
前序遍歷
- Morris建立連接時是給每個根結點尋找其左子樹的最右側結點建立連接，因此“從根結點開始”這一特性很符合前序遍歷“中左右”的遍歷方式，因此在給結點建立連接的同時輸出此根結點即可完成前序遍歷，
特殊處理：
- 建立連接的同時輸出此根結點，
- 到達一些沒有子節點的葉子節點，直接輸出并向右走回傳上層或向此節點的右子樹前進，
- 判斷出某節點已有連接，則不用輸出，直接斷開走過的連接后繼續向右走，
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == NULL)
return ans;
TreeNode* cur1 = root; // 當前的結點
TreeNode* cur2 = NULL; // 當前結點的左子樹
while (cur1 != NULL)
{
cur2 = cur1->left;
// 當前結點的左子樹存在即可建立連接
if (cur2 != NULL)
{
// 找到當前左子樹的最右側節點，并且不能沿著連接回傳上層
while (cur2->right != NULL && cur2->right != cur1)
cur2 = cur2->right;
//最右側節點的右指標沒有指向根結點，創建連接并往下一個左子樹的根結點進行連接操作
if (cur2->right == NULL)
{
cur2->right = cur1;
ans.push_back(cur1->val);
cur1 = cur1->left;
continue; // 這個continue很關鍵
}
else
// 當左子樹的最右側節點有指向根結點，此時說明我們已經進入到了回傳上層的階段，不再是一開始的建立連接階段，同時在回到根結點時我們應已輸出過下層節點，直接斷開連接即可
cur2->right = NULL;
}
else
// 當前節點的左子樹為空，說明左側到頭，直接輸出
ans.push_back(cur1->val);
// 回傳上層的階段不斷向右走
cur1 = cur1->right;
}
return ans;
}
};
中序遍歷
思路：
類似迭代，整個二叉樹中輸出的第一個節點是最左側結點，因此在建立連接的時候是不能夠直接輸出的，必須在建立連接階段完成，到達最左側結點之后回傳上層的階段，才能開始輸出，此時正好符合“左中右”的遍歷方式，
特殊處理：
- 在建立連接階段并不輸出結點，
- 在找到最左側結點（即根結點的左子樹為空）時，開始向右走回傳上層并同時輸出當前結點，
- 對右子樹也進行同樣的處理，
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == NULL)
return ans;
TreeNode* cur1 = root; // 當前的結點
TreeNode* cur2 = NULL; // 當前結點的左子樹
while (cur1 != NULL)
{
cur2 = cur1->left;
// 當前結點的左子樹存在即可建立連接
if (cur2 != NULL)
{
// 找到當前左子樹的最右側節點，并且不能沿著連接回傳上層
while (cur2->right != NULL && cur2->right != cur1)
cur2 = cur2->right;
//最右側節點的右指標沒有指向根結點，創建連接并往下一個左子樹的根結點進行連接操作
if (cur2->right == NULL)
{
cur2->right = cur1;
cur1 = cur1->left;
continue; // 這個continue很關鍵
}
else
// 當左子樹的最右側節點有指向根結點，此時說明我們已經進入到了回傳上層的階段，不再是一開始的建立連接階段，同時在回到根結點時我們應已輸出過下層節點，直接斷開連接即可
cur2->right = NULL;
}
// 當前節點的左子樹為空，說明左側到頭，直接輸出
ans.push_back(cur1->val);
// 回傳上層的階段不斷向右走
cur1 = cur1->right;
}
return ans;
}
};
后序遍歷
思路：
后序遍歷又雙叒叕是最難搞的情況，舉個例子：
- 列印順序：列印 4 列印 5 2 列印 6 列印 7 3 1
- 我們將一個節點的連續右節點當成一個單鏈表來看待，可以發現，輸出順序是將此單鏈表翻轉后輸出，
- 當我們回傳上層之后，也就是將連線斷開的時候，輸出下層的單鏈表，
- 比如回傳到 ２，此時列印 ４
- 比如回傳到 １，此時列印 ５ ２
- 比如回傳到 ３，此時列印 ６
- 那么我們只需要將這個單鏈表逆序輸出即可，
- note：這里不應該列印當前層，而是之前的一層，否則根結點會先與右邊輸出，
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == NULL)
return ans;
TreeNode* curr = root; // 當前的結點
TreeNode* currLeft = NULL; // 當前結點的左子樹
while (curr != NULL) {
currLeft = curr->left;
// 當前結點的左子樹存在即可建立連接
if (currLeft != NULL)
{
// 找到當前左子樹的最右側節點，并且不能沿著連接回傳上層
while (currLeft->right != NULL && currLeft->right != curr)
currLeft = currLeft->right;
//最右側節點的右指標沒有指向根結點，創建連接并往下一個左子樹的根結點進行連接操作
if (currLeft->right == NULL)
{
currLeft->right = curr;
curr = curr->left;
continue; // 這個continue很關鍵
}
// 當左子樹的最右側節點有指向根結點，此時說明我們已經進入到了回傳上層的階段，斷開連接同時對之前的一層進行翻轉并輸出
else
{
currLeft->right = NULL;
postMorrisPrint(curr->left, ans);
}
}
// 回傳上層的階段不斷向右走
curr = curr->right;
}
// 最后一輪回圈結束時，從root結點引申的右結點單鏈表并沒有輸出，這里補上
postMorrisPrint(root, ans);
return ans;
}
//輸出函式
void postMorrisPrint(TreeNode* head, vector<int>& ans) {
TreeNode* newhead = postMorrisReverseList(head); // newhead為翻轉后的新頭部
TreeNode* curr = newhead;
while (curr != NULL)
{
ans.push_back(curr->val);
curr = curr->right;
}
postMorrisReverseList(newhead); // 遍歷結束后再次翻轉恢復原鏈表
}
//翻轉單鏈表函式
TreeNode* postMorrisReverseList(TreeNode* head) {
TreeNode* curr = head;
TreeNode* pre = NULL; // 哨兵結點
while (curr != NULL)
{
TreeNode* next = curr->right;
curr->right = pre;
pre = curr;
curr = next;
}
return pre;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/283167.html
標籤：AI