当前位置：网站首页>【PTA】L2-011 玩转二叉树

【PTA】L2-011 玩转二叉树

2022-04-23 20:20:00 【也许会吧】

原题链接

L2-011 玩转二叉树

解题思路

利用前序遍历和中序遍历的特点进行深搜
深搜退出条件：中序首>=尾不成立
深搜递归：改变根节点，中序首尾指向，存放下标
要点：由前序找到中序的根

ac代码

#include <iostream>
#include <cstring>
using namespace std;
int in[30], pre[30];
int level[100000];//数组要开大一点，因为不是完全二叉树 

void dfs(int root, int start, int end, int index) {
    
	//root前序遍历的首 start,end中序遍历的首尾 index存放的下标
	if(start > end) return;
	
	level[index] = pre[root];//此（子）树的根节点，储存
	
	int i = start;
	while(i < end && in[i] != pre[root]) i++;//找到中序遍历中的根节点 （这也是前序遍历的左右子树分开点）

	dfs(root + 1, start, i - 1, 2 * index + 2);//这里巧妙的将结点换位置，将左边和右边结点换位置。
	dfs(root + (i - start) + 1, i + 1, end, 2 * index + 1);
}

int main() {
    
	memset(level, -1, sizeof(level));

	int n;
	scanf("%d",&n);
	for(int i = 0; i < n; i++) scanf("%d", &in[i]);
	for(int i = 0; i < n; i++) scanf("%d", &pre[i]);

	dfs(0, 0, n - 1, 0);

	int cnt = 0;
	for(int i = 0; i < 10000; i++) {
    
		if(level[i] != -1) {
    
			if(cnt != n - 1) {
    
				printf("%d ", level[i]);
				cnt++;
			} else{
    
				printf("%d", level[i]);
				break;
			}
		}
	}
	return 0;
}

版权声明
本文为[也许会吧]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_55475680/article/details/124355263

边栏推荐

猜你喜欢

随机推荐