首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#12858

二叉树遍历 题目描述 有一棵二叉树,结点数量不超过 26 个,树上的每个结点都有一个大写字母。 给定这棵二叉树的中序遍历及后序遍历,请输出它的前序遍历。 输入格…

二叉树遍历

题目描述

有一棵二叉树,结点数量不超过 26 个,树上的每个结点都有一个大写字母。

给定这棵二叉树的中序遍历及后序遍历,请输出它的前序遍历。

输入格式

第一行:一个字符串,表示二叉树的中序遍历;

第二行:一个字符串,表示二叉树的后序遍历。

输出格式

单独一行:一个字符串,表示二叉树的前序遍历。

输入样例

DBEAC

DEBCA

输出样例

ABDEC

限制

时间限制:1000ms

内存限制:256MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;string&gt; using namespace std; // 中序in, 后序post, 输出前序 void build(string in, string post) {     if (in.empty()) return;     // 后序最后一个是根     char root = post.back();     cout &lt;&lt; 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 &gt;&gt; in &gt;&gt; post;     build(in, post);     return 0; }</pre>
这道题暂未补解析。