03-树3 Tree Traversals Again （c++递归实现）

「爱情、让人受尽委屈。」 2021-10-29 14:56 228阅读 0赞

### 题目 ###

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

#### Input Specification: ####

Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.

#### Output Specification: ####

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

#### Sample Input: ####

6  
Push 1  
Push 2  
Push 3  
Pop  
Pop  
Push 4  
Pop  
Pop  
Push 5  
Push 6  
Pop  
Pop

#### Sample Output: ####

3 4 2 6 5 1

### 题意理解 ###

push的顺序为先序遍历  
pop的顺序为中序遍历  
按照后序遍历输出

### 代码 ###

#include<cstdio>
    #include<stack>
    #include<string>
    #include<iostream>
    using namespace std;
    const int maxn=30;
    int pre[maxn],in[maxn],post[maxn];	//	分别代表前序，中序，后序遍历数组
    
    //PreL 前序遍历数组的位置
    //inL 中序遍历数组的位置
    //postL 后序遍历数组的位置
    void solve(int PreL, int inL, int postL, int n){
    	if(n==0) return;
    	if(n==1){
    		post[postL]=pre[PreL];
    		return;
    	}
    	int i;
    	int root=pre[PreL];			//前序遍历数组的第PreL个数就是根结点
    	post[postL+n-1]=root;		//root是后序遍历数组的第postL+n-1个数
    	for(i=0;i<n;i++){
    		if(in[inL+i]==root) break;	//在中序遍历数组中找到root,记录root所在位置i
    	}	
    	int L=i,R=n-i-1;			//root左边的是左子树，右边的是右子树
    	solve(PreL+1,inL,postL,L);	//递归解决左子树
    	solve(PreL+1+L,inL+L+1,postL+L,R);	//递归解决右子树
    }
    
    
    int main(){
    	int n,num,i=0,j=0;
    	scanf("%d",&n);				//输入一个整数
    	string s;
    	stack<int> st;
    	for(int z=0;z<2*n;z++){		//读入2n行，构建前序遍历和中序遍历的数组
    		cin>>s;					//读入字符串判断入栈或出栈	
    		if(s=="Push"){			//入栈
    			scanf("%d\n",&num); //输入要入栈的数字num
    			st.push(num);		//num入栈
    			pre[i++]=num;		//把num放入前序遍历数组
    		}else{					//出栈
    			num=st.top();			//取出栈顶赋给num
    			st.pop();			//出栈
    			in[j++]=num;		//num赋给中序遍历数组
    		}
    	}
    	solve(0,0,0,n);				//通过前序遍历和中序遍历求二叉树的后序遍历
    	for(i=0;i<n;i++){
    		printf("%d",post[i]);
    		if(i!=n-1) printf(" ");
    	}
    	return 0;
    }

参考了这篇文章里的图 [添加链接描述][Link 1]，画的很清晰。  
一开始找出根节点：  
![在这里插入图片描述][20190816213325186.png]  
递归解决左右子树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]

### 提交结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]

[Link 1]: https://blog.csdn.net/shinanhualiu/article/details/49279051
[20190816213325186.png]: /images/20211029/f6f26f66d44c4663bb8c2116c9283dc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20211029/d271f36384334981a7600cc4efec253a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]: /images/20211029/29eb70fff7a24ca189900080ad0a39a6.png