洛谷 P1030 求先序排列

洛谷 P1030 求先序排列

Description

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

Input

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

Output

• 1行，表示一棵二叉树的先序。

Sample Input

BADC
BDCA

Sample output

ABCD

题解：

• 这道题其实是考概念的。
• 首先先序、中序、后序的定义是根据根的顺序决定的。
• 现有根A，左儿子B，右儿子C。先序：ABC；中序：BAC；后序：BCA
• 你会发现后序为：“左右根”，最后一个元素是根。所以后序的最后元素一定是根。
• 所以根据这个性质，我们可以先找到根，然后在中序中找到根的位置，这样中序就被分成了两个部分：根的左边和根的右边。然后就可以分别把根左边和根右边的中序和后序继续递归下去

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

string a, b;

void dfs(string a, string b)
{
    if(a != "" && b != "")
    {
        char root = b[b.size() - 1];
        cout << root;
        int pos = a.find(root);
        dfs(a.substr(0, pos), b.substr(0, pos));
        dfs(a.substr(pos + 1, a.size() - 1 - pos), b.substr(pos, b.size() - 1 - pos));
    }
}

int main()
{
    cin >> a >> b;
    dfs(a, b);
    return 0;
}