LeetCode145. Post order traversal of binary tree (three methods of recursion and iteration)

LeetCode145. Postorder traversal of binary trees

1. problem

2. Ideas

（1） What is post order traversal

（2） recursive

It's the same as the previous sequence and the middle sequence , Just put the root node to the last access

（3） Iterative thinking

a. Transform preorder traversal

b. Fake middle root traversal

Middle root traversal ：1. From the root node From top to bottom Go down the left branch , And put the nodes along the way Pressing stack , Until the deepest node （ No left child ）.
2. Follow the left passage , Play the stack from bottom to top , Sequential access All nodes along the way And its Right subtree .

As shown in the figure below ：

The post order traversal faces a problem ： Behind the bomb stack , Cannot access immediately p, But first visit p The right subtree , And then visit p. So it needs to be preserved in some way p.
Strategy 1： Don't talk about stack p, Instead, only take the value of the element at the top of the stack .
Strategy 2： Allow nodes to enter and leave the stack multiple times , Instant bomb stack p Then let it enter the stack immediately .

Strategy 1

Strategy 2：

Set a binary in the stack element , Maintain a label i,i Represents the current node / Stack times . Any node in a binary tree p You have to enter the stack three times , Out of stack three times .
The first time out of the stack is for traversal p The left subtree .
The second battle is for traversal p The right subtree .
The third time is to access p.

Operation example
Pseudo code

3. Code implementation

（1） recursive

class Solution
{
    
public:
    void posOrder(TreeNode*cur,vector<int>& vec)
    {
    
         if(cur == NULL)return;
        posOrder(cur->left,vec);// Left 
        posOrder(cur->right,vec);// Right 
        vec.push_back(cur->val);// root 
    }

    vector<int> postorderTraversal(TreeNode* root) {
    
        vector<int> result;
        posOrder(root, result);
        return result;
    }
};

（2） iteration

a. Transform preorder traversal

class Slution{
    
	public:
		vector<int> postorderTraversal(TreeNode* root) {
    
			stack<TreeNode*>st;
			vector<int> result;
			if(root == NULL) return result;
			st.push(root);
			while(!st.empty()){
    
				TreeNode* node = st.pop();
				st.pop();
				result.push_nack(node->val);
				if(node->left st.push(node->left));// Relative to the previous sequence traversal, make a change here  
				if(node->right) st.push(node->right);// Empty nodes do not stack  
			}
			reverse(result.begin(),result.end());// The reverse result is the order of left and right 
			return result; 
		}
}; 

b. Strategy 1

class Solution{
    
	public:
		vector<int> postorderTraversal(TreeNode* root) {
    
		stack<TreeNode*>st;
		vector<int> result;
		TreeNode* p = root; 
		TreeNode* pre = NULL;// pre yes p After the root of the precursor , That is to say p Previously visited nodes 
		while(1){
    
			while(p!=NULL){
    
				st.push(p);
				p = p->left;
			}
			if(st.empty()) return result;
			p = st.top();
            if(p!=NULL){
    
            if( p->right == NULL||pre == p->right)
			{
    
				p = st.top();st.pop();
				result.push_back(p->val);
				pre = p; p = NULL;
			}
			else p = p->right;
		} 
        }
}
};

b. Strategy 2

Use STL：

class Solution{
    
	public:
		vector<int> postorderTraversal(TreeNode* root) {
    
        int flag[512];
        int top = 0;//top Point to the position where the element will be placed   It really doesn't work   because stl There is no change in top
        stack<TreeNode*>st;
		vector<int> result;
		flag[top] = 1;
		st.push(root);
        top++;
		while(!st.empty()){
    
			TreeNode* p = st.top();  
            st.pop();// Out of the stack  
            top--;
			if(flag[top] == 1){
    
				flag[top] = 2; st.push(p); top++;
				if(p!= NULL && p->left != NULL) 
				{
    
					flag[top] = 1;
					st.push(p->left);
                    top++;
				}
			} 
			else if(flag[top] == 2)
			{
    
				flag[top] = 3; st.push(p);top++;
				if(p!=NULL && p->right != NULL){
    
					flag[top] = 1;
					st.push(p->right);
                    top++;
				}
			}
			else if(p!=NULL && flag[top] == 3)
				result.push_back(p->val);
		}
        return result;
}
};

Be careful ！top It needs to be maintained additionally ！stl There's no such thing as int top This kind of thing ！

Don't use STL：

int flag[512];
int top = 0;//top Point to the position where the element will be placed  
class stac{
    
public:
	void InitStack(){
    
		top = 0;
	}
	
	void Push(TreeNode *p){
    
		stack[top++] = p;
	}

    TreeNode* Pop(){
    
    	top--;
        return stack[top];
    }
	
	bool empty() {
    
  		if (top == 0)return true;
 		 return false;
    }
    
     TreeNode* Top( ){
    
        return stack[top-1];
 }
private:
	TreeNode *stack[512];
}; 

class Solution{
    
	public:
		vector<int> postorderTraversal(TreeNode* root) {
    
		stac st;
		st.InitStack();
		vector<int> result;
		flag[top] = 1;
		st.Push(root);
		while(!st.empty()){
    
			TreeNode* p = st.Pop();// Out of the stack  
			if(flag[top] == 1){
    
				flag[top] = 2; st.Push(p);
				if(p!= NULL && p->left != NULL) 
				{
    
					flag[top] = 1;
					st.Push(p->left);
				}
			} 
			else if(flag[top] == 2)
			{
    
				flag[top] = 3; st.Push(p);
				if(p!=NULL && p->right != NULL){
    
					flag[top] = 1;
					st.Push(p->right);
				}
			}
			else if(p!=NULL && flag[top] == 3)
			{
    
				result.push_back(p->val);
			}	
            else
                continue;
		}
        return result;
}
};