题目描述

树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。
假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树的先序遍历字符串。

输入格式

两行，每行是由大写字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和按层遍历的序列。

输出格式

一行，表示二叉树的先序序列。

数据范围

输入字符串的长度均不超过26。

输入样例：

DBEAC
ABCDE

输出样例：

ABDEC

#include<iostream>
#include<algorithm>

using namespace std;

string InOrder, LevelOrder;

//[l1,r1]中序序列，[l2,r2]层序序列
void build(int l1, int r1, int l2, int r2)
{
    if(l1>r1) return;
    int i,j;
    //每次用循环来寻找根
    int root;//中序序列中根节点的位置
    for(i = l2; i<=r2; i++)
    {
        bool flag = false;//标志有没有找到根节点
        for(j = l1; j<=r1; j++)
        {
            if(LevelOrder[i] == InOrder[j])//在中序序列中找到根节点
            {
                cout<<LevelOrder[i];//找到根节点输出
                root = j;
                flag = true;
                break;
            }
        }
        if(flag) break;
    }
    build(l1,root-1,l2+1,r2);//左子树
    build(root+1,r1,l2+1,r2);//右子树
}
int main()
{
    cin >> InOrder >> LevelOrder;
    build(0, InOrder.size() - 1, 0, LevelOrder.size() - 1);
    return 0;
}