文档章节

sicily 1935 二叉树重建

Ciel
 Ciel
发布于 2013/01/16 17:05
字数 749
阅读 176
收藏 0

Description

对于二叉树T,可以递归定义它的先序遍历、中序遍历和后序遍历如下: PreOrder(T)=T的根节点+PreOrder(T的左子树)+PreOrder(T的右子树) InOrder(T)=InOrder(T的左子树)+T的根节点+InOrder(T的右子树) PostOrder(T)=PostOrder(T的左子树)+PostOrder(T的右子树)+T的根节点 其中加号表示字符串连接运算。例如,对下图所示的二叉树,先序遍历为DBACEGF,中序遍历为ABCDEFG。 
输入一棵二叉树的先序遍历序列和中序遍历序列,输出它的广度优先遍历序列。 

Input

第一行为一个整数t(0<t<10),表示测试用例个数。 以下t行,每行输入一个测试用例,包含两个字符序列s1和s2,其中s1为一棵二叉树的先序遍历序列,s2为中序遍历序列。s1和s2之间用一个空格分隔。序列只包含大写字母,并且每个字母最多只会出现一次。 

Output

为每个测试用例单独一行输出广度优先遍历序列。 

Sample Input

2 
DBACEGF ABCDEFG 
BCAD CBAD

Sample Output


DBEACGF 
BCAD

分析:

本题很直白,就是知道二叉树前序和中序遍历的结果,然后输出广度优先遍历的结果。明白二叉树遍历的递归方式就能很明白的看出解法。

对于每棵树或者子树,他的前序和中序遍历序列都有特定的性质,即前序序列开始的节点一定是根节点。那么中序序列中次节点将序列分城左右两个子序列,分别对应左右子树中序遍历结果。如此左右子树节点数目已知,那么就可以在前序序列中找出左右子树前序遍历结果,这样递归处理就能还原二叉树,然后调用BSF方法即可。

PS:二叉树处理方法大都与递归相关,而且递归的中心在于树或者子树的根,牢牢抓住至一点就能化繁为简。另外,其实前序遍历算是广度优先遍历。

代码:

// Problem#: 1935
// Submission#: 1895987
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <string>
#include <queue>
using namespace std;

struct node{
    char left;
    char right;
}buffer[30];

void tree(string str1, string str2) {
    int size = str1.size();
    if (size == 0) return ;
    int a = str2.find(str1[0]);
    int b = str1[0] - 'A';
    string l1, l2, r1, r2;
    l1 = a ? str1.substr(1, a): "";
    l2 = a ? str2.substr(0, a): "";
    r1 = (a < size - 1) ? str1.substr(a + 1, size - 1 - a): "";
    r2 = (a < size - 1) ? str2.substr(a + 1, size - 1 - a): "";
    buffer[b].left = a ? l1[0] : '\0';
    buffer[b].right = (a < size - 1) ? r1[0] : '\0';
    tree(l1, l2);
    tree(r1, r2);
}

void bfs(char c) {
    queue<char> tmp;
    tmp.push(c);
    while (!tmp.empty()) {
        char t = tmp.front();
        cout << t;
        tmp.pop();
        node n = buffer[t - 'A'];
        if (n.left != '\0') tmp.push(n.left);
        if (n.right != '\0') tmp.push(n.right);
    }
}

int main() {
    int t;
    string preOrder, inOrder;
    cin >> t;
    while (t--) {
        cin >> preOrder >> inOrder;
        tree(preOrder, inOrder);
        bfs(preOrder[0]);
        cout << endl;
    }
    return 0;
}

© 著作权归作者所有

上一篇: sicily 1781 Knight
下一篇: sicily 1090 Highways
Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
通过层序和中序遍历序列重建二叉树

  在学二叉树的重建时,在《算法笔记》上学到了如何通过先序(或后序)遍历序列和中序遍历序列重建二叉树,它也提出了一个问题:如何通过层序和中序遍历序列重建二叉树?我一开始按照先序和...

the_sky314
03/28
0
0
【挑战剑指offer】系列04:重建二叉树

题干描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,...

LinkedBear
2018/11/07
12
0
剑指offer 5. 二叉树的下一个节点

原题 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,...

dby_freedom
2018/10/16
0
0
剑指Offer-根据二叉树的前序和后序遍历重建二叉树

原文地址:点击打开链接 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8} 和...

z956281507
2017/12/13
0
0
重构二叉树之前序遍历和中序遍历

题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8} 和中序遍历序列{...

wall--e
2016/04/26
211
0

没有更多内容

加载失败,请刷新页面

加载更多

python学习10.04:Python list列表使用技巧及注意事项

前面章节介绍了很多关于 list 列表的操作函数,细心的读者可能会发现,有很多操作函数的功能非常相似。例如,增加元素功能的函数有 append() 和 extend(),删除元素功能的有 clear()、 remo...

太空堡垒185
26分钟前
4
0
新手插画学习的方法?教你如何自学?

插画学习的方法?教你如何自学? 从小喜欢画一些漫画头像随笔画,但是其实没有基础。个人偏好小清新手绘风的插画(如下图),每每看到都希望自己能画出这样的作品。 我其实很想说画这种美术功...

huihuajiaocheng
32分钟前
4
0
面试题

1、实现clone();

gtandsn
43分钟前
5
0
CentOS 7 部署 tesseract-ocr

官方地址 github yum-config-manager --add-repo https://download.opensuse.org/repositories/home:/Alexander_Pozdnyakov/CentOS_7/ 若提示 yum-config-manager: command not found 执行以......

阿白
43分钟前
3
0
JAVA比较器中comparator的使用

一个专用的比较器Comparator Comparator是一个专用的比较器,当一个不支持自比较或者自比较函数不能满足要求时,可写一个比较器来完成两个对象之间大小的比较。Comparator体现了一种策略模式...

daxiongdi
44分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部