前言
Morris遍历是通过对原二叉树增加虚拟连接（后面会复原）来节约递归或队列的额外空间消耗，通过常数空间即可实现对二叉树的遍历。
本文主要是通过Morris Inorder Traversal of Binary Tree | Morris Preorder Traversal of Binary Tree和Morris Inorder Tree Traversal的讲解。
中序遍历
算法如下图，可以自己画图或者看视频捋捋，
选择节点curr指向根节点，接下来：
- 如果
curr没有左子树，就输出节点，然后一直往右子树走，即left-root-right的中序遍历顺序 - 如果有左子树找到当前节点
curr的前趋节点predecessor，- 如果
redecessor无右子树，就可以将它和当前节点curr链接起来，这样之后可以直接通过right的连接回到curr节点，如L连接到A，然后curr往左走 - 如果有右子树，先复原之前对
predecessor的修改（否则会出现死循环和破坏二叉树的原本结构），输出节点，然后curr继续往右走
- 如果
中序
void morris_inorder_traversal(TreeNode *root)
{
TreeNode *curr = root;
while (curr != NULL)
{
if (curr->left == NULL)
{
cout << curr->val << " ";//输出当前节点
curr = curr->right;
}
else
{
// 找当前节点的前趋结点
TreeNode* predecessor = curr->left;
while (predecessor->right != NULL
&& predecessor->right != curr)
{
predecessor = predecessor->right;
}
// 使当前节点成为inorder的前序节点的右侧子节点
if (predecessor->right == NULL)
{
predecessor->right = curr;
curr = curr->left;
}
//复原之前的修改
else
{
predecessor->right = NULL;
cout << curr->val << " ";//输出当前节点
curr = curr->right;
}
}
}
}前序遍历
前序和中序的区别如下图，即遍历顺序的区别导致输出节点的地方不一样，
inorder是left-root-right,所以输出在curr往右走之前preorder是root-left-right，所以输出在curr往左走之前
而上面一样的部分是因为如果没有左子树，输出是一样的。
前序
void morris_preorder_traversal(TreeNode *root)
{
TreeNode *curr = root;
while (curr != NULL)
{
if (curr->left == NULL)
{
cout << curr->val << " ";
curr = curr->right;
}
else
{
// Find the inorder predecessor of current
TreeNode* predecessor = curr->left;
while (predecessor->right != NULL
&& predecessor->right != curr)
{
predecessor = predecessor->right;
}
// Make current as the right child of its inorder predecessor
if (predecessor->right == NULL)
{
predecessor->right = curr;
cout << curr->val << " ";
curr = curr->left;
}
// Revert the changes, fix the right child of predecessor
else
{
predecessor->right = NULL;
curr = curr->right;
}
}
}
}后序遍历
使用Morris遍历后序则没有前序和中序那么简单，在stackoverflow，有人提出了一个简单的方法：做与preorder morris遍历对称相反的工作，以相反的顺序打印节点。
逻辑是前序是root-left-right,如果逆反遍历的左右方向，则得到的遍历顺序是root-right-left，再反一次顺序即left-right-root，而后序遍历是left-right-root。
后序
TreeNode* node = root;
stack<int> s;//需要有一个遍历存储路径，当然也可以用vector存储，然后翻转
while(node) {
if(!node->right) {//这里就不需要输出了
s.push(node->val);
node = node->left;
}
else {
TreeNode* prev = node->right;//predecessor
while(prev->left && prev->left != node)//这里与preorder相反
prev = prev->left;
if(!prev->left) {//同上
prev->left = node;
s.push(node->val);//
node = node->right;
}
else {//同上
node = node->left;
prev->left = NULL;
}
}
}
while(!s.empty()) {//倒序输出
cout << s.top() << " ";
s.pop();
}
cout << endl;力扣题目二叉树遍历题目
标签：predecessor,node,遍历,curr,前中,Morris,right,left From： https://www.cnblogs.com/fudanxi/p/16852740.html