1086. Tree Traversals Again (25)时间限制200 ms内存限制65536 kB代码长度限制16000 B判题程序Standard作者CHEN, YueAn 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.Figure 1Input 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:6Push 1Push 2Push 3PopPopPush 4PopPopPush 5Push 6PopPopSample Output:3 4 2 6 5 1
提交代码
//这道题在看陈越老师的数据结构时候已经做过了，现在又做了一遍，感觉也是不同了，这次对树的遍历又有了更深的理解，这次栈也没用，
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<stack>#include<algorithm>using namespace std;const int maxn=1000007;typedef long long ll;template<class T>inline T read(T&x){char c;while((c=getchar())<=32);bool f=false;if(c=='-')f=true,c=getchar();for(x=0; c>32; c=getchar())x=x*10+c-'0';if(f)x=-x;return x;}template<class T>inline void write(T x){if(x<0)putchar('-');else if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');}template<class T>inline void writeln(T x){write(x);puts("");}//——–IO template——————–#define lson (root<<1)//左儿子#define rson ((root<<1)+1)//右儿子int a[maxn];//存树的节点bool vis[maxn];//标记节点是否访问过，因为树在遍历时回溯的时候会用到int first=1;void post(int root){if(a[lson]!=-1)post(lson);if(a[rson]!=-1)post(rson);if(first)printf("%d",a[root]),first=0;else printf(" %d",a[root]);}int main(){int n,m,i,j,k,t,x;read(n);m=n<<1;memset(a,-1,sizeof(a));char op[5];int root=1;int ok=0;for(i=0;i<m;i++){scanf("%s",op);if(strcmp(op,"Push")==0){read(x);if(a[root]!=-1)//是回溯的回来访问的，这时读入的节点必然是这个节点的右儿子{root=rson;//找到有儿子a[root]=x;//赋值root=lson;//root更新到左儿子，因为输入的时候先序}else //不是回溯访问的 ，那么就是第一次访问的，，所以这个时候节点的值就是他{a[root]=x;//节点赋值root=lson;//root更新到左儿子}}else{root/=2;//pop就是回溯，所以回到父亲的节点x=a[root];while(vis[x])//判断是不是已经访问过了，如果访问过了，那么还要继续回溯到第一个没有访问的节点，这个由样例的4到1，而不是4再到2了{2root/=2;x=a[root];}if(!vis[x])vis[x]=1;//标记访问过的}}post(1);//后序遍历 ，比较简单了，直接递归printf("\n");return 0;}
人生不如意十之八-九，与其诅咒黑暗，倒不如在生命中点燃一盏灯
