Morris traversal of binary tree

If you can modify the original tree, you can use morris Traverse , because morris Traversal using the leaf node null pointer to achieve ;

A node with a left tree can be reached twice , Determine the number of times to return to the node according to the direction of the rightmost node of the left subtree ,

1. Morris Ergodic order

#include<iostream>
#include<vector>

using namespace std;

class TreeNode
{
    
public:
	TreeNode* left;
	TreeNode* right;
	int val;

	TreeNode(int v){
    val = v;left = nullptr;right = nullptr;}
	TreeNode(){
    val = 0; left = nullptr; right = nullptr;}
};

void Morris(TreeNode* root)
{
    
	TreeNode* cur = root;
	TreeNode* mostnode = nullptr;
	while (cur != nullptr)
	{
    
		mostnode = cur->left;
		if (mostnode != nullptr)
		{
    
			while (mostnode != nullptr && mostnode->right != cur)
			{
    
				mostnode = mostnode->right;
			}
			// For the first time cur
			if (mostnode->right == nullptr)
			{
    
				cout<<cur->val<<" ";
				mostnode->right = cur;
				cur = cur->left;
				continue;
			}
			// Come to... For the second time cur
			else
			{
    
				cout<<cur->val<<" ";
				mostnode->right = nullptr;
			}
		}
		else
			cur = cur->right;
	}
}

• moris The first sequence traversal
  morris Traverse , Each node with a left subtree will arrive twice , It is specified that only when a node is reached for the first time , To achieve traversal ;

• code

#include<iostream>
#include<vector>

using namespace std;

class TreeNode
{
    
public:
	TreeNode* left;
	TreeNode* right;
	int val;

	TreeNode(int v){
    val = v;left = nullptr;right = nullptr;}
	TreeNode(){
    val = 0; left = nullptr; right = nullptr;}
};

void Morris(TreeNode* root)
{
    
	TreeNode* cur = root;
	TreeNode* mostnode = nullptr;
	while (cur != nullptr)
	{
    
		mostnode = cur->left;
		if (mostnode != nullptr)
		{
    
			while (mostnode != nullptr && mostnode->right != cur)
			{
    
				mostnode = mostnode->right;
			}
			// For the first time cur
			if (mostnode->right == nullptr)
			{
    
				cout << cur->val << " "; // The first sequence traversal 
				mostnode->right = cur;
				cur = cur->left;
				continue;
			}
			// Come to... For the second time cur
			else
			{
    
				mostnode->right = nullptr;
			}
		}
		else
			cur = cur->right;
	}
}

2.Morris In the sequence traversal

• Thought analysis
  Only once , Print directly ; Reach the node twice , Second arrival print

• code

#include<iostream>
#include<vector>

using namespace std;

class TreeNode
{
    
public:
	TreeNode* left;
	TreeNode* right;
	int val;

	TreeNode(int v){
    val = v;left = nullptr;right = nullptr;}
	TreeNode(){
    val = 0; left = nullptr; right = nullptr;}
};

void Morris(TreeNode* root)
{
    
	TreeNode* cur = root;
	TreeNode* mostnode = nullptr;
	while (cur != nullptr)
	{
    
		mostnode = cur->left;
		if (mostnode != nullptr)
		{
    
			while (mostnode != nullptr && mostnode->right != cur)
			{
    
				mostnode = mostnode->right;
			}
			// For the first time cur
			if (mostnode->right == nullptr)
			{
    
				mostnode->right = cur;
				cur = cur->left;
				continue;
			}
			// Come to... For the second time cur
			else
			{
    
				mostnode->right = nullptr;
			}
		}
		cout << cur->val << " "; // In the sequence traversal 
		cur = cur->right;
	}
}

3.Morris After the sequence traversal

• Ideas
  When a node arrives twice , Print the bounded tree of the left subtree of the node in reverse order ; Finally, print the right boundary of the whole tree in reverse order ; When printing the right boundary of the tree in reverse order , Need to reverse the right boundary right Pointer pointing , Restore after printing

• code

#include<iostream>
#include<vector>

using namespace std;

class TreeNode
{
    
public:
	TreeNode* left;
	TreeNode* right;
	int val;
	TreeNode(int v){
    val = v;left = nullptr;right = nullptr;}
	TreeNode(){
    val = 0; left = nullptr; right = nullptr;}
};

TreeNode* reverse_Tree(TreeNode* node)
{
    
	TreeNode* pre = nullptr;
	TreeNode* cur = node;
	
	while (cur != nullptr)
	{
    
		TreeNode* temp = cur->right;
		cur->right = pre;
		pre = cur;
		cur = temp;
	}
	return pre;
}

void printEdge(TreeNode* root)
{
    

	TreeNode* node= reverse_Tree(root);
	TreeNode* cur = node;
	while (cur!= nullptr)
	{
    
		cout << cur->val << " ";
		cur = cur->right;
	}
	TreeNode* temp = reverse_Tree(node);
}

void Morris(TreeNode* root)
{
    
	TreeNode* cur = root;
	TreeNode* mostnode = nullptr;
	while (cur != nullptr)
	{
    
		mostnode = cur->left;
		if (mostnode != nullptr)
		{
    
			while (mostnode != nullptr && mostnode->right != cur)
			{
    
				mostnode = mostnode->right;
			}
			// For the first time cur
			if (mostnode->right == nullptr)
			{
    
				mostnode->right = cur;
				cur = cur->left;
				continue;
			}
			// Come to... For the second time cur
			else
			{
    
				mostnode->right = nullptr;
				printEdge(cur->left);
			}
		}
		cur = cur->right;
	}
	printEdge(root);
	return;
}

4. Morris Traversal judgment search binary tree

When traversing a binary tree , Node values are always in ascending order , So the tree in this lesson is the search binary tree

Edge ergodic , Edge judgment

• code

#include<iostream>
#include<vector>

using namespace std;

class TreeNode
{
    
public:
	TreeNode* left;
	TreeNode* right;
	int val;

	TreeNode(int v){
    val = v;left = nullptr;right = nullptr;}
	TreeNode(){
    val = 0; left = nullptr; right = nullptr;}
};

bool is_BST(TreeNode* root)
{
    
	TreeNode* cur = root;
	TreeNode* mostnode = nullptr;
	int preValue = INT_MIN;
	while (cur != nullptr)
	{
    
		mostnode = cur->left;
		if (mostnode != nullptr)
		{
    
			while (mostnode != nullptr && mostnode->right != cur)
			{
    
				mostnode = mostnode->right;
			}
			// For the first time cur
			if (mostnode->right == nullptr)
			{
    
				mostnode->right = cur;
				cur = cur->left;
				continue;
			}
			// Come to... For the second time cur
			else
			{
    
				mostnode->right = nullptr;
			}
		}
		if(cur->val < prevalue)
			return false;
		prevalue = cur->val;
		cur = cur->right;
	}
	return true;
}

5. Regression traversal and Morris When to use traversal

When we must realize the strong integration of binary tree to complete the problem , Recursion must be used ; For example, you must get information from the left subtree of a node , Then take the information from the right subtree , Then we can get the result ; This means that a node has reached three times , This problem must be traversed recursively ;