Non recursive traversal of binary tree

Preorder traversal of two tree

Title List ： Preorder traversal of two tree

Title Description

Give you the root node of the binary tree root , Of its node value Before the order Traverse .

Topic analysis

Non recursive implementation of preorder traversal of binary tree , Here, you can define a stack to store to nodes . The order of preorder traversal is about the root , So according to the last in, first out principle of the stack , You can stack each node first , Then take out the top elements in turn , Stack them in turn , And traverse the nodes in the right subtree . The specific code implementation is as follows ：

Code implementation

vector<int> preorderTraversal(TreeNode* root) 
{
    
	vector<int> ret;
	stack<TreeNode*> st;
	TreeNode* cur = root;
	while (cur || !st.empty())
	{
    
		while (cur)
		{
    
			st.push(cur);
			ret.push_back(cur->val);
			cur = cur->left;
		}
		TreeNode* tmp = st.top();
		st.pop();
		cur = tmp->right;
	}
	return ret;
}

Middle order traversal of binary trees

Topic link ： Middle order traversal of binary trees

Title Description

Given the root node of a binary tree root , return its Middle preface Traverse .

Topic analysis

The normal recursive implementation of the middle order traversal of the binary tree only needs to be implemented in the order of the left root and the right , Here we try to realize the middle order traversal of binary tree by non recursion . The middle order traversal of a binary tree is similar to the previous order , The difference is that a first in root node is a first in left node , Pay attention to vector It's just a matter of time , The code implementation is as follows ：

Code implementation

vector<int> inorderTraversal(TreeNode* root) 
{
    
	vector<int> ret;
	stack<TreeNode*> st;
	TreeNode* cur = root;
	while (cur || !st.empty())
	{
    
		while (cur)
		{
    
			st.push(cur);
			cur = cur->left;
		}
		TreeNode* tmp = st.top();
		ret.push_back(tmp->val);
		st.pop();
		cur = tmp->right;

	}
	return ret;
}

Postorder traversal of binary trees

Topic link ： Postorder traversal of binary trees

Title Description

Give you the root node of a binary tree root , Returns the After the sequence traversal .

Topic analysis

Normally, it is very simple to use recursion to realize the post order traversal of binary tree , Just follow the order of left and right roots , However, if the recursion depth of this tree is too deep, it may cause stack overflow , This problem can be solved in a non recursive way . How to realize post order traversal of binary tree non recursively ？ It is different from preorder and inorder traversal , He needs to access the left node and the right node before accessing the root , So here we need to make a mark , Whether the right subtree node of this node has been accessed , If so, you can traverse the root , If not already visited , You need to access the right subtree node first , The code implementation is as follows ：

Code implementation

    vector<int> postorderTraversal(TreeNode* root) 
    {
    
	vector<int> ret;
	stack<TreeNode*> st;
	TreeNode* cur = root;
	TreeNode* prev = nullptr;
	while (cur || !st.empty())// Enter the loop when neither is empty 
	{
    
		while (cur)// When the node is not empty , The left subtree node is put on the stack 
		{
    
			st.push(cur);
			cur = cur->left;
		}
		TreeNode* tmp = st.top();
		if (tmp->right == nullptr || tmp->right == prev)
		{
    
			ret.push_back(tmp->val);
			prev = tmp;
			st.pop();
		}
		else
		{
    
			cur = tmp->right;
		}
	}
	return ret;
    }