UVA-10410 树重建 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

我个人认为，题目思路的思考比较难。

首先我尝试使用类似于二叉树中序与前后序遍历来还原树的方法做，但是发现

1. 失败的情形太多，可能一颗子树需要用多种不同的方式构建尝试。

2. 即使子树成功，更大的子树也可能失败，需要再重新按照别的方案构建更小的子树，且方式不同。

因此这个路走不通。

后来查看了一些题解也没理解，有些还用到了栈，也不知道为什么要用。后来看到了这篇，感觉使用的方法较简单，也很清楚。

UVA10410 树重建 Tree Reconstruction - _CHO - 洛谷博客

这里还是解释一下我用的方法：

有结点a和b。设结点a的bfs，dfs位置分别为bfs[a],dfs[a]
使用dfs序列，从尾向前遍历，设当前遍历到的结点为b。
我们从b开始往前找，找到b的父节点。在找到父节点的过程中，我们会碰到这几类结点，设为a：
1. b的前序兄弟结点
    此时在bfs中，bfs[b] = bfs[a] + 1，且a < b
2. b的前序兄弟结点的子节点
    此时在bfs中，bfs[a] > bfs[b]。即节点肯定在BFS中的下一层。
3. b的父节点
    此时在bfs中，bfs[b] >= bfs[a] + 1
 

因此，当找到结点a为bfs[b] = bfs[a] + 1，且a < b时，即有可能是兄弟结点，也有可能是父节点。这时候无法判断。我参考的方法中是将其作为了前序兄弟结点。我尝试过，如果把这种情况作为父节点，题目给出的样例可以通过，但是提交后是WA。

因此这里为什么直接认为是前序兄弟结点，还并不清楚。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std; 

int n;
int bfs[1010];
int bfsPos[1010];
int dfs[1010];
int dfsPos[1010];

int near[1010]; 
vector<int> arr[1010];


void constructTree() {
	if(n < 2) return;
	int i, j, k;
	for(i = n-1; i > 1; --i) {
		for(j = i-1; j >= 0; --j) {
			if(bfsPos[dfs[i]] == bfsPos[dfs[j]] + 1 && dfs[i] > dfs[j]) {
				near[dfs[j]] = dfs[i];
				break;
			}
			if(bfsPos[dfs[i]] >= bfsPos[dfs[j]] + 1) {
				arr[dfs[j]].push_back(dfs[i]);
				break;
			}
		}
	}
	arr[dfs[0]].push_back(dfs[1]);
	for(i = 0; i < n; ++i) {
		for(j = 0; j < arr[i].size(); ++j) {
			if(near[arr[i][j]]) arr[i].push_back(near[arr[i][j]]);
		}
	}
}

int main() {
	int i, j;
	while(scanf("%d", &n) == 1 && n > 0) {
		for(i = 0; i < n; ++i) scanf("%d", &bfs[i]);
		for(i = 0; i < n; ++i) scanf("%d", &dfs[i]);
		for(i = 0; i < n; ++i) {
			bfsPos[bfs[i]] = i;
			dfsPos[dfs[i]] = i;
		}
		for(i = 1; i <= n; ++i) {
			arr[i] = vector<int>();
			near[i] = 0;
		}
		constructTree();
		for(i = 1; i <= n; ++i) {
			sort(arr[i].begin(), arr[i].end());
			printf("%d:", i);
			for(j = 0; j < arr[i].size(); ++j) printf(" %d", arr[i][j]);
			putchar('n');
		}
	}
	return 0;
}