Morris traversal

The traditional traversal method is either recursive or stack , The space complexity of its traversal is O(N), and Morris Traversal can be done with O(1) Spatial complexity of , And its time complexity is the same as that of the traditional method O(N).

---

Morris Traversal introduction

Morris Traversal uses a large number of free pointers in the original tree , To save space .

Morris The traversal rule is ：
Suppose the current node cur, At the beginning of the cur Go to the position of the head node

1. If cur There is no left child ,cur To the right （cur=cur->right）
2. If cur There are left children , Find the rightmost node on the left subtree mostRight
   1). If mostRight The right pointer of points to null , Make it point cur, then cur Move to the left （cur=cur->left）
   2). If mostRight The right pointer of points to cur, Make it point nullptr, then cur To the right (cur=cur->right)
3. cur It's empty time , Stop traversal .

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 by cur The rightmost node of the left tree 
	Node* mostRight = nullptr;
	while (cur != nullptr)
	{
    
		mostRight = cur->left;
		// If cur No left tree , that cur Will move directly to the right 
		if (mostRight != nullptr)
		{
    
			// look for cur The rightmost node of the left tree , When empty or equal to cur Stop when 
			while (mostRight->right != nullptr && mostRight->right != cur)
			{
    
				mostRight = mostRight->right;
			}
			// If it is empty , Explain the first time to the rightmost node , Now point the pointer to cur
			// then cur Move to left subtree 
			if (mostRight->right == nullptr)
			{
    
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			// here mostRight->right == cur
			// Indicates the second arrival at the node , Recover the pointer of this node 
			else
			{
    
				mostRight->right = nullptr;
			}
		}
		cur = cur->right;
	}
}

Morris The first sequence traversal

The order of preorder traversal is about the root , because Morris Traversal may reach a node twice , So we need to print the first time we reach the node .

void morrisPre(Node* head)
{
    
	if (head == nullptr)
	{
    
		return;
	}
	Node* cur = head;
	//mostRight by cur The rightmost node of the left tree 
	Node* mostRight = nullptr;
	while (cur != nullptr)
	{
    
		mostRight = cur->left;
		// If cur No left tree , that cur Will move directly to the right 
		if (mostRight != nullptr)
		{
    
			// look for cur The rightmost node of the left tree , When empty or equal to cur Stop when 
			while (mostRight->right != nullptr && mostRight->right != cur)
			{
    
				mostRight = mostRight->right;
			}
			// If it is empty , Explain the first time to the rightmost node , Now point the pointer to cur
			// then cur Move to left subtree 
			if (mostRight->right == nullptr)
			{
    
				cout << cur->value << endl;
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			// here mostRight->right == cur
			// explain mostRight Arrive at this node for the second time , Recover the pointer of this node 
			else
			{
    
				mostRight->right = nullptr;
			}
		}
		//cur There is no left tree , Print directly cur, And then move cur To right subtree 
		else
		{
    
			cout << cur->value << endl;
		}
		cur = cur->right;
	}
}

Morris In the sequence traversal

Middle order traversal follows the principle of left root right , For a node , Print on second arrival .

void morrisIn(Node* head)
{
    
	if (head == nullptr)
	{
    
		return;
	}
	Node* cur = head;
	//mostRight by cur The rightmost node of the left tree 
	Node* mostRight = nullptr;
	while (cur != nullptr)
	{
    
		mostRight = cur->left;
		// If cur No left tree , that cur Will move directly to the right 
		if (mostRight != nullptr)
		{
    
			// look for cur The rightmost node of the left tree , When empty or equal to cur Stop when 
			while (mostRight->right != nullptr && mostRight->right != cur)
			{
    
				mostRight = mostRight->right;
			}
			// If it is empty , Explain the first time to the rightmost node , Now point the pointer to cur
			// then cur Move to left subtree 
			if (mostRight->right == nullptr)
			{
    
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			// here mostRight->right == cur
			// explain mostRight Arrive at this node for the second time , Recover the pointer of this node 
			else
			{
    
				mostRight->right = nullptr;
			}
		}
		// Because the first time mostRight->right = cur;
		// So the left subtree cur You can reach this node twice , Print the second time 
		cout << cur->value << endl;
		
		cur = cur->right;
	}
}

Morris After the sequence traversal

Postorder traversal is the order of left and right roots , Because we didn't set the parent pointer , Therefore, it is impossible to print from the right subtree to the root node . Unless the stack structure is used in reverse order , But this violates the space complexity of O（1） The purpose of .

therefore , We need to flip the linked list , Point the right pointer to its parent node , Change back after printing .

// Flip list 
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)
{
    
	// Regard the rightmost part of the right subtree as a linked list 
	// Flip the linked list 
	Node* tail = reverseEdge(head);
	Node* cur = tail;
	while (cur != nullptr)
	{
    
		cout << cur->value << endl;
		cur = cur->right;
	}
	// Turn the linked list back 
	reverseEdge(tail);
}
void morrisPos(Node* head)
{
    
	if (head == nullptr)
	{
    
		return;
	}
	Node* cur = head;
	//mostRight by cur The rightmost node of the left tree 
	Node* mostRight = nullptr;
	while (cur != nullptr)
	{
    
		mostRight = cur->left;
		// If cur No left tree , that cur Will move directly to the right 
		if (mostRight != nullptr)
		{
    
			// look for cur The rightmost node of the left tree , When empty or equal to cur Stop when 
			while (mostRight->right != nullptr && mostRight->right != cur)
			{
    
				mostRight = mostRight->right;
			}
			// If it is empty , Explain the first time to the rightmost node , Now point the pointer to cur
			// then cur Move to left subtree 
			if (mostRight->right == nullptr)
			{
    
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			// here mostRight->right == cur
			// Indicates the second arrival at the node , Recover the pointer of this node 
			else
			{
    
				mostRight->right = nullptr;
				// Print the right boundary of the left subtree of a tree in reverse order 
				printEdge(cur->left);
			}
		}

		cur = cur->right;
	}
	// Print the right boundary of the whole tree in reverse order 
	printEdge(head);
}