ACMCLUB問題B:二叉樹問題
テーマの説明
現在、二叉の木を与えられた順序は、シーケンスと中間シーケンスを経て、二叉の木の高さを計算するように要求されます.
入力フォーマット
複数のセットのテストデータを入力し、各グループの入力は、まず正の整数N(<=50)を与え、ツリー内の総点の総数とする.次の2行は、先の順序と中の順序が連続して与えられています.長さがNの文字列は、繰り返し英字(大文字と小文字を区別する)を含まない文字列です.
出力
各グループの入力に対して、1つの整数が出力されます.すなわち、2つのツリーの高さです.
サンプル入力
9 ABDFGHIEC FDHGIBEAC 7 Abcdefg gfedbA
サンプル出力
5 7
数日前に、ポストの順序と中間の順序に基づいて、ツリーのテーマを作成しました.ここは前の順序と中の連続のツリーのテーマです.そして、ツリーの高さを統計します.http://blog.csdn.net/iaccepted/article/details/20473661
現在、二叉の木を与えられた順序は、シーケンスと中間シーケンスを経て、二叉の木の高さを計算するように要求されます.
入力フォーマット
複数のセットのテストデータを入力し、各グループの入力は、まず正の整数N(<=50)を与え、ツリー内の総点の総数とする.次の2行は、先の順序と中の順序が連続して与えられています.長さがNの文字列は、繰り返し英字(大文字と小文字を区別する)を含まない文字列です.
出力
各グループの入力に対して、1つの整数が出力されます.すなわち、2つのツリーの高さです.
サンプル入力
9 ABDFGHIEC FDHGIBEAC 7 Abcdefg gfedbA
サンプル出力
5 7
数日前に、ポストの順序と中間の順序に基づいて、ツリーのテーマを作成しました.ここは前の順序と中の連続のツリーのテーマです.そして、ツリーの高さを統計します.http://blog.csdn.net/iaccepted/article/details/20473661
#include
#include
#include
using namespace std;
const int maxx = 52;
typedef struct Tree{
Tree *le;
Tree *ri;
char data;
}Tree;
Tree *root;
char pre[maxx],in[maxx];
int Height(Tree *root,int height){
if(root==NULL)return height;
int lheight = Height(root->le,height+1);
int rheight = Height(root->ri,height+1);
return lheight>rheight?lheight:rheight;
}
Tree *buildTree(int pl,int pr,int il,int ir){
if(pl>pr)return NULL;
int p = il;
while(in[p]!=pre[pl])++p;
Tree *tree = (Tree *)malloc(sizeof(Tree));
tree->data = pre[pl];
tree->le = buildTree(pl+1,pl+p-il,il,p-1);
tree->ri = buildTree(pl+p-il+1,pr,p+1,ir);
return tree;
}
void printPre(Tree *root){
if(root==NULL)return;
printf("%d ",root->data);
printPre(root->le);
printPre(root->ri);
}
int main(){
int n,i,height;
Tree *root;
while(scanf("%d%*c",&n)!=EOF){
for(i=0;i