求二叉树的层次遍历

求二叉树的层次遍历

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem De ion

已知一颗二叉树的前序遍历和中序遍历，求二叉树的层次遍历。

Input

输入数据有多组，输入T，代表有T组测试数据。每组数据有两个长度小于50的字符串，第一个字符串为前序遍历，第二个为中序遍历。

Output

每组输出这颗二叉树的层次遍历。

Sample Input

2
abc
bac
abdec
dbeac

Sample Output

abc
abcde

题目链接：

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2711/pid/2824

#include <bits/stdc++.h>

using namespace std;

typedef struct treenode{
    char s;
    struct treenode *leftnode;
    struct treenode *rightnode;
}node;

node *create(char *s1,char *s2,int len)
{
    if(len==0)
    return NULL;
    node *root;
    root=new node;
    int pos=0;
    root->s=*s1;
    while(s2[pos]!=*s1)
    pos++;
    root->leftnode=create(s1+1,s2,pos);
    root->rightnode=create(s1+pos+1,s2+pos+1,len-(pos+1));
    return root;
}

void cengxu(node *root)
{
    int in=0,out=0;
    node *dl[66];
    dl[in++]=root;
    while(in>out)
    {
        if(dl[out])
        {
            cout << dl[out]->s;
            dl[in++]=dl[out]->leftnode;
            dl[in++]=dl[out]->rightnode;
        }
        out++;
    }
    cout << endl;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        char str1[51],str2[51];
        cin >> str1 >> str2;
        int len=strlen(str1);
        node *root=create(str1,str2,len);
        cengxu(root);
    }
    return 0;
}