---

L2-035 完全二叉树的层序遍历(完全二叉树+后序推出层序)

原创 于 2024-04-03 11:27:02 发布 · 粉丝可见 · 1.3k 阅读 · 23 · 12 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/137332474

本题链接： PTA | 程序设计类实验辅助教学平台

题目：

样例：

cobol<br/>8<br/>91 71 2 34 10 15 55 18<br/>

18 34 55 71 2 10 15 91

思路：

根据题意，这是个完全二叉树+ 后序遍历，要求推出层序遍历。

根据完全二叉树的特性：

设当前结点为 n ，则该左节点 = 2 * n ，  右结点 = 2 * n + 1

后序遍历特性：

对于任意节点，其左子树和右子树都会先被访问，然后才是该节点本身。

所以，对完全二叉树进行后序遍历，遍历顺序为先遍历左子树，再遍历右子树，最后访问根节点。

通过结合这两个特点，我们根据样例画个图。分析一下：

我们再根据题目要求的层序遍历，写个对应的层序数组。

结合： 完美二叉树图 + 后序数组 i 对应关系 + 层序数组 i 关系。

我们可以找到一些规律。

在这里，我们也应该吸取经验。以后遇到完美二叉树的时候，尝试将这些 图 以及对应的数组画出来，结合 完美二叉树的特点

从 后序数组 i 开始，结合 完美二叉树的特点，

l = i << 1          等于向上查找 的 后序遍历的左结点，

r = (i << 1) + 1    等于向上查找 的 后序遍历的右结点，

比如 :

i = 1,          l = 2,           r = 3 i = 2,          l = 4,           r = 5 i = 3,          l = 6,           r = 7 i = 4,          l = 8,           r = 9 i = 5,          l = 10,         r = 11 i = 6,          l = 12,         r = 13 i = 7,          l = 14,         r = 15 i = 8,          l = 16,         r = 17

通过上面的后序遍历下标结合完美二叉树特点，我们试着从 1 开始DFS递归向上查找：

i = 1,          l = 2,           r = 3 i = 2,          l = 4,           r = 5 i = 4,          l = 8,           r = 9 i = 8,          l = 16,         r = 17 i = 5,          l = 10,         r = 11 i = 3,          l = 6,           r = 7 i = 6,          l = 12,         r = 13 i = 7,          l = 14,         r = 15

我们可以发现，每次向上查找到 根结点 i 之后，就是相应层序遍历tree的 第 i 个 对应的查找到第 n  次根节点的后序遍历的值

例如：

到达根节点 i =  8 后：91 == a[1] = tree[8]        第 n = 1 次 查找到根节点

到达根节点 i =  4 后：71 == a[2] = tree[4]        第 n = 2 次 查找到根节点

到达根节点 i = 5 后：  2  == a[3] = tree[5]        第 n = 3 次 查找到根节点

到达根节点 i = 2 后： 34 == a[4] = tree[2]        第 n = 4 次 查找到根节点

到达根节点 i = 6 后： 10 == a[5] = tree[6]        第 n = 5 次 查找到根节点

到达根节点 i = 7 后： 15 == a[6] = tree[7]        第 n = 6 次 查找到根节点

到达根节点 i = 3 后： 55 == a[7] = tree[3]        第 n = 7 次 查找到根节点

最后回到根节点 i = 1 后： 18 == a[8] = tree[1]        第 n = 8 次 查找到根节点

所以结合以上规律可以得到，完美二叉树 + 后序 推出层序规律：

从后序数组的 1 的底结点开始向上递归查找，查找到的 第 n 个结点就是相应的下标 i 层序结点

最后代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();
 
signed main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}
int n,t = 1,a[N],tree[N];
void DFS(int i)
{
	if(i > n) return ;//递归边界，以及找到相应的根节点了。
	
	int l = i << 1;	// 向上查找 L 左父结点
	int r = (i << 1) + 1;	// 向上查找 R 右父结点
	
	DFS(l);	// 开始向上 L 查找
	DFS(r);	// 开始向上 R 查找
	
	// 已经查找到 第 t 个结点，
	// 开始赋值相应层序遍历的 i 值为后序遍历的 a[t]值
	tree[i] = a[t++];	
}
 
inline void solve()
{
	cin >> n;
	for(int i = 1;i <= n;++i) cin >> a[i];
	
	DFS(1);	// 从低结点 1 开始查找
	
	// 输出答案
	for(int i = 1;i <= n;++i)
	{
		if(i != 1) cout << ' ';
		cout << tree[i];
	}
}

最后提交：​​​​​​​