首页 > 代码库 > UVa536 Tree Recovery (二叉树遍历)
UVa536 Tree Recovery (二叉树遍历)
链接：http://acm.hust.edu.cn/vjudge/problem/19645
分析：三种树的遍历方式中除了中序外再知道另外遍历方式得到的序列就可以唯一确定一棵二叉树。
先序：先打印根再遍历左右子树。
中序：先遍历左子树，然后打印根，再遍历右子树。
后序：先遍历左右子树，最后打印根。
1 #include <cstdio> 2 #include <cstring> 3 4 char pre_order[30], in_order[30]; 5 6 void dfs(int L1, int R1, int L2, int R2) { 7 char root = pre_order[L1]; 8 int p = L2; 9 while (in_order[p] != root) p++;10 int cnt1 = p - L2, cnt2 = R2 - p;11 if (cnt1) dfs(L1 + 1, L1 + cnt1, L2, p - 1);12 if (cnt2) dfs(R1 - cnt2 + 1, R1, p + 1, R2);13 printf("%c", root);14 }15 16 int main() {17 while (scanf("%s", pre_order) == 1) {18 scanf("%s", in_order);19 int n = strlen(pre_order);20 dfs(0, n - 1, 0, n - 1);21 printf("\n");22 }23 return 0;24 }
UVa536 Tree Recovery (二叉树遍历)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。