Tree Reconstruction UVA - 10410 (根据树的BFS和DFS建树)

悠悠 2022-02-21 02:11 168阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70][]

解题思路:

题目给出了一棵树的层序遍历和先序遍历

我们取依次取先序遍历的一个结点a和这个结点的下一个结点b。

然后分类讨论:

1.如果a为根节点,那么b必定为a的子节点,那么我们将b的父节点设为a,

更新a的子结点序列

2.如果b在层序遍历中的位置正好在a的后面一个,那么我们可以断定b为a的子结点或者为a的兄弟结点,由于题目要求层序遍历是从小到大排的,那么

通过比较a,b的大小可以确定关系

如果b大于a,那么b是a的兄弟结点

如果b小于a,那么b是a的子结点

3.如果b在层序遍历中的位置在a的后面,那么b肯定是a的子结点

4.如果b在层序遍历中的位置在a的前面,那么b可能为a的祖先结点的子结点

我们在二叉树中回溯a结点的父节点,回溯到a的祖先结点在层序遍历中的位置在b前面时,此时a的祖先结点为b的祖先结点,这时,我们再根据2中的步骤判断即可。

本题用到了回溯思想,一个结点的父节点可以用前驱数组保存,结点在层序遍历中的位置也可以用数组保存。

#define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <stack>
    #include <algorithm>
    #include <string.h>
    #include <vector>
    #include <queue>
    #include <stdio.h>
    #include <stack>
    using namespace std;
    const int MAXN = 10010;
    int N;
    int layerOrders[MAXN];
    int preOrders[MAXN];
    vector<int> subNodes[MAXN];
    //位置索引
    int posIndexes[MAXN];
    int sfFather[MAXN];  //父节点前驱
    void initSet() {
    	for (int i = 1; i <= N; ++i) {
    		sfFather[i] = i;   //
    	}
    }
    int main() {
    	while (scanf("%d", &N) != EOF) {
    		memset(subNodes, 0, sizeof(subNodes));
    		initSet();  //初始化
    		for (int i = 0; i < N; ++i) {
    			scanf("%d", &layerOrders[i]);   //层序便利
    			posIndexes[layerOrders[i]] = i;  //更新位置索引用来判断
    		}
    		for (int i = 0; i < N; ++i) {
    			scanf("%d", &preOrders[i]);     //先序遍历
    		}
    		//根据先序判断
    		for (int j = 0; j < N - 1; ++j) {
    			int u = preOrders[j];
    			int v = preOrders[j + 1];
    			if (j == 0) {  //特殊:根节点的情况:下一个结点必为子节点
    				subNodes[u].push_back(v);
    				sfFather[v] = u;  //更新父节点
    				continue;
    			}
    			//层序判断
    			//第一种情况:层序中u+1 == v,判断大小
    			if (posIndexes[u] + 1 == posIndexes[v]) {
    				//如果v的值大于u,那么就是兄弟结点
    				if (v > u) {
    					subNodes[sfFather[u]].push_back(v);
    					sfFather[v] = sfFather[u];  
    				}
    				//如果v的值小于u,那么就是子节点
    				else {
    					subNodes[u].push_back(v);
    					sfFather[v] = u;
    				}
    			}
    			//第二种情况:v在u的较后面:子节点
    			else if (posIndexes[v] - posIndexes[u] > 0) {
    				subNodes[u].push_back(v);
    				sfFather[v] = u;
    			}
    			else if (posIndexes[v] - posIndexes[u] < 0) {   //第三种情况:v在u的前面:回溯
    				int ti = j - 1;
    				int curNode = preOrders[ti];
    				while (posIndexes[v] - posIndexes[curNode] < 0) {
    					ti--;
    					curNode = preOrders[ti];  //往前回溯
    				}
    				//回溯完毕,调用1中的算法
    				if (posIndexes[curNode] + 1 == posIndexes[v]) {
    					if (v > curNode) {
    						subNodes[sfFather[curNode]].push_back(v);  
    						sfFather[v] = sfFather[curNode];
    					}
    					else {
    						subNodes[curNode].push_back(v);
    						sfFather[v] = curNode;
    					}
    				}
    				else if (posIndexes[v] - posIndexes[curNode] > 0) {
    					subNodes[curNode].push_back(v);
    					sfFather[v] = curNode;
    				}
    			}
    		}
    		for (int i = 1; i <= N; ++i) {
    			printf("%d:", i);
    			for (int j = 0; j < subNodes[i].size(); ++j) {
    				printf(" %d", subNodes[i][j]);
    			}
    			printf("\n");
    		}
    	}
    	system("PAUSE");
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70]: /images/20220221/290cbd75bc6c4bf5be299bf048e33035.png