Tree Recovery,UVa536
程序员文章站
2024-03-19 09:21:10
...
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;
const int MAXN = 100+10;
char pre_order[MAXN], in_order[MAXN];
char lch[MAXN], rch[MAXN];
char build_tree(int L1, int R1, int L2, int R2);
void post_order(char a);
int main()
{
while(cin>>pre_order){
cin>>in_order;
int n = strlen(pre_order);
build_tree(0,n-1,0,n-1);
post_order(pre_order[0]);
cout<<endl;
}
return 0;
}
//把pre_order[L1.....R1]和post_order[L2..R2]建成一棵树返回树根
char build_tree(int L1, int R1, int L2, int R2)
{
if(L2>R2) return '0';
char root;
root = pre_order[L1];
int p = L2;
while(in_order[p] != root ) p++;
int cnt = p-L2;
lch[root-'A'] = build_tree(L1+1,L1+cnt,L2,p-1);
rch[root-'A'] = build_tree(L1+cnt+1, R1, p+1, R2);
return root;
}
void post_order(char a){
if(lch[a-'A'] != '0') post_order(lch[a-'A']);
if(rch[a-'A'] != '0') post_order(rch[a-'A']);
cout<<a;
return;
}
上一篇: md5加密工具类
下一篇: 2019.8.4 JZ DAY4总结
推荐阅读
-
Tree Recovery,UVa536
-
flex tree的展开,关闭,添加、删除子节点 博客分类: Flex FlexXML.netBlog
-
Data Structures - Segment Tree
-
Luogu P2619 [国家集训队2]Tree I 凸优化,wqs二分
-
Is It A Tree?
-
java.lang.NoClassDefFoundError: javax.swing.tree.TreeNode is a restricted class
-
2020 牛客暑期多校 第二场 C-Cover the Tree(dfs序)
-
2020牛客暑期多校第二场 C - Cover the Tree(思维/贪心)
-
2020牛客暑期多校训练营(第二场)Cover the Tree
-
2020牛客多校第二场C Cover the Tree(dfs序)