1339:【例3-4】求后序遍历

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 4439 通过数: 3025
【题目描述】
输入一棵二叉树的先序和中序遍历序列,输出其后序遍历序列。

【输入】
共两行,第一行一个字符串,表示树的先序遍历,第二行一个字符串,表示树的中序遍历。树的结点一律用小写字母表示。

【输出】
一行,表示树的后序遍历序列。

【输入样例】
abdec
dbeac
【输出样例】
debca

#include <iostream>
#include <string>
using namespace std;



void rebuild(string s1, string s2)
{
    int minn=0x7fffffff;
    int add=-1;
    for(int i=0;i<s2.length();i++)
    {
        int temp=(int)s1.find(s2[i]);
        if(temp < minn)
        {
            minn=temp;
            add=i;
        }
    }
    string s3=s2.substr(0,add);
    string s4=s2.substr(add+1,s2.length());
    if(s3.length()<=1)
        cout<<s3;
    else
        rebuild(s1,s3);
    if(s4.length()<=1)
        cout<<s4;
    else
        rebuild(s1,s4);
    cout<<s1[minn];
}

int main()
{
    string s1,s2;
    cin>>s1>>s2;
    rebuild(s1,s2);
}

Last modification:January 17th, 2021 at 12:01 pm