求二叉树的先序遍历

╰+攻爆jí腚メ 2022-05-14 03:40 129阅读 0赞

Time Limit: 1000 ms Memory Limit: 65536 KiB  
Submit Statistic  
Problem Description  
已知一棵二叉树的中序遍历和后序遍历，求二叉树的先序遍历  
Input  
输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的中序遍历序列，第二个字符串表示二叉树的后序遍历序列。  
Output  
输出二叉树的先序遍历序列  
Sample Input  
2  
dbgeafc  
dgebfca  
lnixu  
linux  
Sample Output  
abdegcf  
xnliu  
Hint

Source  
GYX

#include <iostream>
    //#include <string>
    //#include <typeinfo>
    //#include <algorithm>
    #include <cstring>
    using namespace std;
    typedef struct nd
    {
        char data;
        nd *left, *right;
    } node, *pnode;
    
    
    pnode zhonghou(char hou[],int len,char zhong[])
    {
        if(len<=0)
            return NULL;
        pnode root = nullptr;
        root=new node();
        root->data=hou[len-1];
        int p;//根的下标
        for(p=0; p<len; p++)
            if(zhong[p]==hou[len-1])
                break;
        root->left=zhonghou(hou,p,zhong);
        root->right=zhonghou(hou+p,len-p-1,zhong+p+1);
        return root;
    };
    
    
    
    void xian(pnode root)
    {
        if(root)
        {
            cout << root->data;
            xian(root->left);
            xian(root->right);
        }
    }
    
    int main()
    
    {
    
        int t;
        char zhong[1000],hou[1000];
        pnode root = nullptr;
        cin >>t;
        while(t--)
        {
            cin >> zhong >> hou;
            int len =strlen(zhong);
            root=zhonghou(hou,len,zhong);
            xian(root);
            cout << endl;
        }
    
        return 0;
    
    }