UVa 10410

Tree Reconstruction

from Chapter 3. Data Structures :: Fundamental Data Structures :: Exercises: Beginner

Problem

给你一个结点数为N（1 ≤ N ≤ 1000）的树的BFS遍历序列和DFS遍历序列，求出这个树的形状。按从小到大输出1~N结点的儿子，如有多组解，输出任意一组即可。

Solution

我们用DFS[M:N]来表示DFS序列从下标M到N的子序列切片。我们可以先把DFS[1:N]放入一个队列，代表我们需要去求解的整个树。显然，DFS[1:N]的第一个数字就是根节点的编号，之后我们的任务就是利用BFS序列找到根节点的几个子树，将其放入队列中继续求解。

那么如何利用BFS来找子树呢？这时候，我们用队列来放子树的好处就体现出来了，由于队列中访问子树的顺序和BFS的顺序一样，BFS序列中节点的顺序正是我们访问每个子树时根节点出现的顺序。再利用各子树的根节点将子树分割开来扔入队列中，待队列不再有子树，我们的任务就完成了。

该算法的时间复杂度平均为O(NlogN)，最坏情况下为O（N^2）。但由于题目只要求任意一组解，几乎不会形成最坏情况。