A17484. 二叉树遍历
填空题
困难
知识点
题目描述
二叉树遍历
题目描述
有一棵二叉树，结点数量不超过 26 个，树上的每个结点都有一个大写字母。
给定这棵二叉树的中序遍历及后序遍历，请输出它的前序遍历。
输入格式
第一行：一个字符串，表示二叉树的中序遍历；
第二行：一个字符串，表示二叉树的后序遍历。
输出格式
单独一行：一个字符串，表示二叉树的前序遍历。
输入样例
DBEAC
DEBCA输出样例
ABDEC参考答案
#include <iostream>
#include <string>
using namespace std;
// 中序in, 后序post, 输出前序
void build(string in, string post) {
if (in.empty()) return;
// 后序最后一个是根
char root = post.back();
cout << root;
int pos = in.find(root);
// 递归左右
build(in.substr(0, pos), post.substr(0, pos));
build(in.substr(pos+1), post.substr(pos, in.size()-pos-1));
}
int main() {
string in, post;
cin >> in >> post;
build(in, post);
return 0;
}
上一题
下一题