#1049 : 后序遍历
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在参与过了美食节之后，小Hi和小Ho在别的地方又玩耍了一阵子，在这个过程中，小Ho得到了一个非常有意思的玩具——一棵由小球和木棍连接起来的二叉树！
小Ho对这棵二叉树爱不释手，于是给它的每一个节点都标记了一个标号——一个属于A..Z的大写字母，并且没有任意两个节点的标号是一样的。小Hi也瞅准了这个机会，重新巩固了一下小Ho关于二叉树遍历的基础知识~就这样，日子安稳的过了两天。
这天，小Ho正好在求解这棵二叉树的前序、中序和后序遍历的结果，但是却在求出前序遍历和中序遍历之后不小心把二叉树摔到了地上，小球和木棍等零件散落了一地！
小Ho损失了心爱的玩具，正要嚎啕大哭起来，所幸被小Hi发现了，劝说道：“别着急，这不是零件都还在么？拼起来不就是了？”
“可是我忘记了二叉树长什么样子了！”小Ho沮丧道。
“这个简单，你不是刚刚求出了这棵二叉树的前序和中序遍历的结果么，利用这两个信息就可以还原出整棵二叉树来哦！”
“这样么？！！”小Ho止住了泪水，问道：“那要怎么做呢？”
没错！小Ho在这一周遇到的问题便是：给出一棵二叉树的前序和中序遍历的结果，还原这棵二叉树并输出其后序遍历的结果。
提示：分而治之——化大为小，化小为无
输入
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第一行为一个由大写英文字母组成的字符串，表示该二叉树的前序遍历的结果。
每组测试数据的第二行为一个由大写英文字母组成的字符串，表示该二叉树的中序遍历的结果。
对于100%的数据，满足二叉树的节点数小于等于26。
输出
对于每组测试数据，输出一个由大写英文字母组成的字符串，表示还原出的二叉树的后序遍历的结果。
样例输入
AB
BA
样例输出BA
| #include <iostream> |
| #include <cstring> |
| #include <string> |
| #include <set> |
| #include <map> |
| using namespace std; |
| struct TreeNode |
| { |
| char left; |
| char right; |
| TreeNode(){ left = 0; right = 0; } |
| }; |
| char BuildTree(string a, string b, TreeNode * Tree/*, char * characterPrev, char * characterMiddle*/){ |
| char root=a[0]; /*根节点*/ |
| if (a.length() == 1){ |
| return root; |
| } |
| int rootIndex = b.find(root); /*查找root在中序中的位置*/ |
| string MiddleLeft = b.substr(0, rootIndex); |
| string MiddleRight = b.substr(rootIndex+1, b.length() - rootIndex-1); |
| string PrevLeft = a.substr(1, rootIndex); |
| string PrevRight = a.substr(rootIndex + 1, b.length() - rootIndex - 1); |
| if (MiddleLeft.length() > 0){ |
| Tree[root].left = BuildTree(PrevLeft, MiddleLeft, Tree); |
| } |
| else{ |
| Tree[root].left = 0; |
| } |
| if (MiddleRight.length() > 0){ |
| Tree[root].right = BuildTree(PrevRight, MiddleRight, Tree); |
| } |
| else{ |
| Tree[root].right = 0; |
| } |
| return root; |
| } |
| void printTree(char root,TreeNode * Tree){ |
| char l = Tree[root].left; |
| char r = Tree[root].right; |
| if (l != 0){ |
| printTree(l, Tree); |
| } |
| if (r != 0){ |
| printTree(r, Tree); |
| } |
| cout << root; |
| } |
| int main() |
| { |
| string a, b; /*输入数据*/ |
| TreeNode * Tree= new TreeNode['Z'+1]; /*还原树*/ |
| char root; /*根节点*/ |
| cin >> a >> b; |
| root = BuildTree(a, b, Tree); |
| printTree(root, Tree); |
| } |
代码地址
https://github.com/iptop/hihoCoderProblemSolving/blob/master/1049/main.cpp
