题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

BADC
BDCA

输出 #1复制

ABCD

#include <bits/stdc++.h>
using namespace std;

void dfs(string a,string b)
{
    if(a.size()){
        char c = b[b.size()-1];//递归寻找后序遍历的最后一个字符为分界线
        cout<<c;//最后一个字符就是根节点 也就先序遍历的第一个节点
        int k = a.find(c);//记录根的位置
        dfs(a.substr(0,k),b.substr(0,k));//找左子树的根 0->k-1是中序遍历的左子树 k是中序遍历的根节点
        dfs(a.substr(k+1),b.substr(k,b.size()-k-1));//找右子树的根 k+1->结尾都是中序遍历的右子树 后序遍历的从k->结尾-1
    }
}
int main()
{
    string inOrder,after;
    cin>>inOrder>>after;
    dfs(inOrder,after);
    return 0;
}