题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数≤8）。

输入格式

共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式

共一行一个字符串，表示一棵二叉树的先序。

样例输入

BADC
BDCA

样例输出

ABCD

说明/提示

【题目来源】

NOIP 2001 普及组第三题

参考代码

#include <iostream>
#include <cstdio>
#include <string>
#define ll long long
using namespace std;
void pre(string s1, string s2)
{ll l;char root;int pos;l = s1.length();root = s2[l - 1];cout<<root; for(int i = 0; i < l; i++){if(s1[i] == root){pos = i;break;}}if(pos >= 1)pre(s1.substr(0, pos), s2.substr(0, pos));	if(l - 1 - pos >= 1) pre(s1.substr(pos + 1, l - 1 - pos), s2.substr(pos, l - 1 - pos));
} int main()
{string s1, s2;cin>>s1>>s2;pre(s1, s2);return 0;
}