2062 - CC老师的提问
在课堂上,cc老师在讲授数据结构中有关树的遍历问题,现在老师提问同学门,如果给出树的中序遍历,和前序遍历让求出这个树的后序遍历是什么.(给定前序遍历与中序遍历能够唯一确定后序遍历) D / \ / \ B E / \ \ / \ \ A C G / / F 我们举个简单的例子来说, 给出你这个树的前序是DBACEGF 中序遍历是ABCDEFG,那么这个树的后序就是 ACBFGED。 那么现在你些一个程序来快速的回答老师的问题.
Input
有多组测试数据,每组数据一行,先给出树的前序遍历,然后是中序,中间空格分开,没有多余的空格.以EOF作为输入结束
Output
输出这个树的后序遍历.
Examples
Input
DBACEGF ABCDEFG BCAD CBAD
Output
ACBFGED CDAB
Solution C++
#include <bits/stdc++.h> using namespace std; void f(string a, string b) { if (a.size() == 0) return; char root = a[0]; int pos = b.find(root); f(a.substr(1, pos), b.substr(0, pos)); f(a.substr(pos + 1), b.substr(pos + 1)); cout << root; } int main() { string a, b; while (cin >> a >> b) { f(a, b); cout << endl; } return 0; }