问题描述

给定一棵有根二叉树与每个节点为根的子树的大小。一个节点为根的子树定义为从这个节点按照所给的边遍历能达到所有节点所组成的一棵树，树的大小为树里节点的个数。

输入格式

• 第一行一个整数n，代表树的节点数。树上节点编号从1~n。
• 接下来n行，每行两个数a，b。第i行的两个数表示编号为i-1的节点的左儿子为a，右儿子为b。若为0表示没有该儿子。
• 数据保证为一棵合法的有根树。

输出格式

• 输出共4行，每行n个数。
• 第1～3行分别为该树的前序遍历，中序遍历和后序遍历。 　　第4行第i个数为编号为i的节点为根的子树的大小。 样例输入

5
0 0
4 5
1 2
0 0
0 0

样例输出

3 1 2 4 5
1 3 4 2 5
1 4 5 2 3
1 3 5 1 1

数据规模和约定

　　对于100%的数据：1<=n<=10^5。 90分挑错

#include<bits/stdc++.h>
using namespace std;
struct node
{
  long long data,dad,l,r;
}t[1000009];
long long cnt;
void a(long long u){
  if(u==0){
    return ;
	}
 printf("%lld ",t[u].data);
  a(t[u].l);    
  a(t[u].r);  
  
}
void b(long long u)
{
  if(u==0)
    return ;
  b(t[u].l);    
  printf("%lld ",t[u].data);
  b(t[u].r);   
  
}
void c(long long u)
{
  if(u==0)
    return ;
  c(t[u].l);   
  c(t[u].r); 
  printf("%lld ",t[u].data);
}
void find(long long u){
  if(u==0){
    return ;
	}
  cnt++;
  find(t[u].l);    
  find(t[u].r);  
  
}
int main()
{
  long long v,l,r,n;
  scanf("%lld",&n); 
  for(long long  i=1;i<=n;i++){
     t[i].dad=-1;
  }
  for(long long  i=1;i<=n;i++){
      scanf("%lld%lld",&l,&r); 
  	t[i].data=i;
  	t[i].l=l;
  	t[i].r=r;
  	if(l!=0){
  	   t[l].dad=i;
  	}
  	if(r!=0){
  	   t[r].dad=i;
  	}
  } 
  int start; 
  for(long long  i=1;i<=n;i++){
  	if(t[i].dad==-1){
  	   start=t[i].data;
  	}
  }
  //cout<<root<<endl;
  a(start);
  cout<<endl;
 	b(start);
  cout<<endl;
  c(start);
  cout<<endl;
  for(long long  i=1;i<=n;i++){
  	cnt=0;
  	find(t[i].data);
  	//cout<<i<<endl;
  	printf("%lld ",cnt);
  }
  return 0;
}