Morris遍历

传统的遍历方式不管是用递归实现还是用栈实现，其遍历的空间复杂度都是O(N)，而Morris遍历能够做到只用O(1)的空间复杂度，并且其时间复杂度和传统方式一样都是O(N)。

---

Morris遍历介绍

Morris遍历利用原树中大量的空闲指针的方式，来达到节省空间的目的。

Morris遍历的规则为：
假设当前节点cur，开始时cur来到头结点的位置

1. 如果cur没有左孩子，cur向右移动（cur=cur->right）
2. 如果cur有左孩子，找到左子树上的最右节点mostRight
   1).如果mostRight的右指针指向空，让其指向cur，然后cur向左移动（cur=cur->left）
   2).如果mostRight的右指针指向cur，让其指向nullptr，然后cur向右移动(cur=cur->right)
3. cur为空时，停止遍历。

class Node
{
    
public:
	Node(int _value)
	{
    
		value = _value;
		left = nullptr;
		right = nullptr;
	}

	int value;
	Node* left;
	Node* right;
};
void morris(Node* head)
{
    
	if (head == nullptr)
	{
    
		return;
	}
	Node* cur = head;
	//mostRight为cur左树的最右节点
	Node* mostRight = nullptr;
	while (cur != nullptr)
	{
    
		mostRight = cur->left;
		//如果cur没有左树，那么cur会直接向右移动
		if (mostRight != nullptr)
		{
    
			//找cur左树的最右节点，当为空或者等于cur时停止
			while (mostRight->right != nullptr && mostRight->right != cur)
			{
    
				mostRight = mostRight->right;
			}
			//如果为空，说明第一次到最右节点，此时将指针指向cur
			//然后cur向左子树移动
			if (mostRight->right == nullptr)
			{
    
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			//此时mostRight->right == cur
			//说明第二次到达该节点，恢复该节点的指针
			else
			{
    
				mostRight->right = nullptr;
			}
		}
		cur = cur->right;
	}
}

Morris先序遍历

先序遍历的顺序是根左右，由于Morris遍历可能会到达一个节点两次，所以我们需要在第一次到达节点时就打印。

void morrisPre(Node* head)
{
    
	if (head == nullptr)
	{
    
		return;
	}
	Node* cur = head;
	//mostRight为cur左树的最右节点
	Node* mostRight = nullptr;
	while (cur != nullptr)
	{
    
		mostRight = cur->left;
		//如果cur没有左树，那么cur会直接向右移动
		if (mostRight != nullptr)
		{
    
			//找cur左树的最右节点，当为空或者等于cur时停止
			while (mostRight->right != nullptr && mostRight->right != cur)
			{
    
				mostRight = mostRight->right;
			}
			//如果为空，说明第一次到最右节点，此时将指针指向cur
			//然后cur向左子树移动
			if (mostRight->right == nullptr)
			{
    
				cout << cur->value << endl;
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			//此时mostRight->right == cur
			//说明mostRight第二次到达该节点，恢复该节点的指针
			else
			{
    
				mostRight->right = nullptr;
			}
		}
		//cur没有左树的情况，直接打印cur，然后移动cur到右子树上
		else
		{
    
			cout << cur->value << endl;
		}
		cur = cur->right;
	}
}

Morris中序遍历

中序遍历遵循左根右的原则，对于一个节点，第二次到达时打印。

void morrisIn(Node* head)
{
    
	if (head == nullptr)
	{
    
		return;
	}
	Node* cur = head;
	//mostRight为cur左树的最右节点
	Node* mostRight = nullptr;
	while (cur != nullptr)
	{
    
		mostRight = cur->left;
		//如果cur没有左树，那么cur会直接向右移动
		if (mostRight != nullptr)
		{
    
			//找cur左树的最右节点，当为空或者等于cur时停止
			while (mostRight->right != nullptr && mostRight->right != cur)
			{
    
				mostRight = mostRight->right;
			}
			//如果为空，说明第一次到最右节点，此时将指针指向cur
			//然后cur向左子树移动
			if (mostRight->right == nullptr)
			{
    
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			//此时mostRight->right == cur
			//说明mostRight第二次到达该节点，恢复该节点的指针
			else
			{
    
				mostRight->right = nullptr;
			}
		}
		//由于第一次的时候mostRight->right = cur;
		//因此左子树的cur可以到达该节点两次，第二次时进行打印
		cout << cur->value << endl;
		
		cur = cur->right;
	}
}

Morris后序遍历

后序遍历是左右根的顺序，由于我们没有设置父指针，因此没法从右子树往根节点打印。除非使用栈结构逆序，但是这违背了空间复杂度为O（1）的初衷。

因此，我们需要把链表进行翻转，将右指针指向它的父亲节点，打印完以后再改回来。

//翻转链表
Node* reverseEdge(Node* from)
{
    
	Node* pre = nullptr;
	Node* next = nullptr;
	while (from != nullptr)
	{
    
		next = from->right;
		from->right = pre;
		pre = from;
		from = next;
	}
	return pre;
}
void printEdge(Node* head)
{
    
	//将右子树的最右边看成一个链表
	//将链表翻转
	Node* tail = reverseEdge(head);
	Node* cur = tail;
	while (cur != nullptr)
	{
    
		cout << cur->value << endl;
		cur = cur->right;
	}
	//链表再翻转回去
	reverseEdge(tail);
}
void morrisPos(Node* head)
{
    
	if (head == nullptr)
	{
    
		return;
	}
	Node* cur = head;
	//mostRight为cur左树的最右节点
	Node* mostRight = nullptr;
	while (cur != nullptr)
	{
    
		mostRight = cur->left;
		//如果cur没有左树，那么cur会直接向右移动
		if (mostRight != nullptr)
		{
    
			//找cur左树的最右节点，当为空或者等于cur时停止
			while (mostRight->right != nullptr && mostRight->right != cur)
			{
    
				mostRight = mostRight->right;
			}
			//如果为空，说明第一次到最右节点，此时将指针指向cur
			//然后cur向左子树移动
			if (mostRight->right == nullptr)
			{
    
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			//此时mostRight->right == cur
			//说明第二次到达该节点，恢复该节点的指针
			else
			{
    
				mostRight->right = nullptr;
				//逆序打印一棵树左子树的右边界
				printEdge(cur->left);
			}
		}

		cur = cur->right;
	}
	//逆序打印整棵树的右边界
	printEdge(head);
}