【1119】Pre- and Post-order Traversals (30分)

法1

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      const int maxn = 10000+5;
     
    
   

    

     

    
    

     

      bool isUnique;
     
    
   

    

     

    
    

     

      int pre[maxn], post[maxn];
     
    
   

    

     

    
    

     

      int left[maxn], right[maxn];
     
    
   

    

     

    
    

     

      int ans[maxn], nodes;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //return root 
     
    
   

    

     

    
    

     

      int reBuild(int prel, int prer, int postl, int postr) {
     
    
   

    

     

    
    

     
    if(prel > prer) return -1;
     
    
   

    

     

    
    

     
    int root = pre[prel];
     
    
   

    

     

    
    

     
    if(prel == prer) { //leaf
     
    
   

    

     

    
    

     
        return root;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    //left-tree
     
    
   

    

     

    
    

     
    int l1 = prel+1, r2;
     
    
   

    

     

    
    

     
    for(r2 = postl; r2 < postr; r2++) {//在后序中寻找根结点
     
    
   

    

     

    
    

     
        if(post[r2] == pre[l1]) {
     
    
   

    

     

    
    

     
            break;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    int len = r2 - postl + 1;
     
    
   

    

     

    
    

     
    // check unique
     
    
   

    

     

    
    

     
    if(len == prer-prel) {
     
    
   

    

     

    
    

     

              isUnique = false;
     
    
   

    

     

    
    

     
		//若非叶子结点只有左子树/右子树则不唯一
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    int r1 = l1 + len -1;
     
    
   

    

     

    
    

     
    int l2 = postl;
     
    
   

    

     

    
    

     
    //rebulid left-tree
     
    
   

    

     

    
    

     

          left[root] = reBuild(l1, r1, l2, r2);
     
    
   

    

     

    
    

     
    //rebuild right-tree
     
    
   

    

     

    
    

     

          right[root] = reBuild(r1+1, prer, r2+1, prer-1);
     
    
   

    

     

    
    

     
    return root;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void getInorder(int root) {
     
    
   

    

     

    
    

     
    if(root == -1) return;
     
    
   

    

     

    
    

     
    getInorder(left[root]);//递归左子树
     
    
   

    

     

    
    

     

          ans[nodes++] = root;
     
    
   

    

     

    
    

     
    getInorder(right[root]);//递归右子树
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main() {
     
    
   

    

     

    
    

     
    int n;
     
    
   

    

     

    
    

     
    while(scanf("%d", &n) == 1) {
     
    
   

    

     

    
    

     

              isUnique = true;
     
    
   

    

     

    
    

     
        memset(left, -1, sizeof(left));//赋初值
     
    
   

    

     

    
    

     
        memset(right, -1, sizeof(right));
     
    
   

    

     

    
    

     
        for(int i = 0; i < n; i++) {
     
    
   

    

     

    
    

     
            scanf("%d", &pre[i]);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        for(int i = 0; i < n; i++) {
     
    
   

    

     

    
    

     
            scanf("%d", &post[i]);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        int root = reBuild(0, n-1, 0, n-1);
     
    
   

    

     

    
    

     

              nodes = 0;
     
    
   

    

     

    
    

     
        getInorder(root);
     
    
   

    

     

    
    

     
        if(isUnique) {
     
    
   

    

     

    
    

     
            printf("Yes\n");
     
    
   

    

     

    
    

     

              } else {
     
    
   

    

     

    
    

     
            printf("No\n");
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        for(int i = 0; i < nodes; i++) {
     
    
   

    

     

    
    

     
            printf("%d%c", ans[i], i == nodes-1 ? '\n' : ' ');
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

法2

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      using namespace std;  
     
    
   

    

     

    
    

     

      //确定树唯一：除了叶结点以外的每个结点都有两个孩子
     
    
   

    

     

    
    

     

      int n,len;
     
    
   

    

     

    
    

     

      vector<int> pre(10000),post(10000),in(10000);
     
    
   

    

     

    
    

     

      //int pre[35],post[35],in[35];
     
    
   

    

     

    
    

     

      int getIn(int prel,int prer,int postl,int postr){
     
    
   

    

     

    
    

     
	if(prel>prer)  return 0;//非法数据
     
    
   

    

     

    
    

     
	if(prel==prer){
     
    
   

    

     

    
    

     
		//若遍历左右相等则说明此子树为叶结点~直接加入中序遍历序列
     
    
   

    

     

    
    

     

      		in[++len]=pre[prel];
     
    
   

    

     

    
    

     
		return 1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	int i;
     
    
   

    

     

    
    

     
	for(i=postl;i<postr;i++){
     
    
   

    

     

    
    

     
		if(post[i]==pre[prel+1])  break;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	int ok=1;
     
    
   

    

     

    
    

     

      	ok &= getIn(prel+1,prel+i-postl+1,postl,i);
     
    
   

    

     

    
    

     
	//递归左子树
     
    
   

    

     

    
    

     

      	in[++len]=pre[prel];
     
    
   

    

     

    
    

     

      	ok &=getIn(prel+i-postl+2,prer,i+1,postr-1);
     
    
   

    

     

    
    

     
	//递归右子树
     
    
   

    

     

    
    

     
	return ok;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(){   
     
    
   

    

     

    
    

     
	int n;
     
    
   

    

     

    
    

     
	scanf("%d",&n);//结点个数
     
    
   

    

     

    
    

     

      	pre.resize(n+1),post.resize(n+1);
     
    
   

    

     

    
    

     
	for(int i=1;i<=n;i++)
     
    
   

    

     

    
    

     
		scanf("%d",&pre[i]);
     
    
   

    

     

    
    

     
	for(int i=1;i<=n;i++)
     
    
   

    

     

    
    

     
		scanf("%d",&post[i]);
     
    
   

    

     

    
    

     
	puts(getIn(1,n,1,n)?"Yes":"No");
     
    
   

    

     

    
    

     
	//for(int i=1;i<=in.size();i++)
     
    
   

    

     

    
    

     
	for(int i = 1; i <= len; i++)
     
    
   

    

     

    
    

     
		printf("%d%c",in[i],i==len?'\n':' ');
     
    
   

    

     

    
    

     
	system("pause");
     
    
   

    

     

    
    

     
    return 0;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

法3

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      //树不唯一：一个结点只有左子树或者右子树
     
    
   

    

     

    
    

     

      //查找得到的先根序列中根节点的下一结点在后根序列中的位置正好等于right-1
     
    
   

    

     

    
    

     

      int N,pre[30],post[30];
     
    
   

    

     

    
    

     

      vector<int>in;
     
    
   

    

     

    
    

     

      bool flag=true;//表示树的形态唯不唯一
     
    
   

    

     

    
    

     

      void inOrder(int root,int left,int right){//得到中序序列
     
    
   

    

     

    
    

     
	if(left>=right){
     
    
   

    

     

    
    

     
		if(left==right)//如果只有一个结点
     
    
   

    

     

    
    

     

      			in.push_back(pre[root]);
     
    
   

    

     

    
    

     
		return;//直接返回
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	int i=left;
     
    
   

    

     

    
    

     
	while(i<=right-1&&post[i]!=pre[root+1])
     
    
   

    

     

    
    

     
	//查找先序序列中根结点的下一结点在后序序列中的位置
     
    
   

    

     

    
    

     

      		i++;
     
    
   

    

     

    
    

     
	if(i==right-1)
     
    
   

    

     

    
    

     
	//先序序列中根结点的下一结点在后序序列中的位置正好等于right-1
     
    
   

    

     

    
    

     

      		flag=false;//树的形态不唯一
     
    
   

    

     

    
    

     
	inOrder(root+1,left,i);//递归遍历左子树
     
    
   

    

     

    
    

     

      	in.push_back(pre[root]);//将根结点压入中序序列
     
    
   

    

     

    
    

     
	inOrder(root+i-left+2,i+1,right-1);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
	scanf("%d",&N);
     
    
   

    

     

    
    

     
	for(int i=0;i<N;i++)
     
    
   

    

     

    
    

     
		scanf("%d",&pre[i]);
     
    
   

    

     

    
    

     
	for(int i=0;i<N;i++)
     
    
   

    

     

    
    

     
		scanf("%d",&post[i]);
     
    
   

    

     

    
    

     
	inOrder(0,0,N-1);
     
    
   

    

     

    
    

     
	printf("%s\n",flag==true?"Yes":"No");
     
    
   

    

     

    
    

     
	for(int i=0;i<in.size();i++)
     
    
   

    

     

    
    

     
		printf("%s%d",i>0?" ":"",in[i]);
     
    
   

    

     

    
    

     
	printf("\n");
     
    
   

    

     

    
    

     
	system("pause");
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/104030565