1020 Tree Traversals (25 分)

题目传送门：1020 Tree Traversals (25 分)

一、题目大意

给出二叉树的后序遍历和中序遍历，求二叉树的按层遍历。

二、解题思路

要想知道按层遍历的结果，只需要在遍历二叉树的过程中将每个节点的值存到数组对应下标里就行了。通常我们对二叉树的标号都是根节点的下标为1。如果当前点的下标是i，则其左孩子的下标是$2\ast i$，右孩子的下标为$2\ast i+1$。

dfs遍历这个二叉树：

void dfs( int pb, int pe, int ib, int ie, int root){
	if(pb > pe){
		return;
	}
	traversal[root] = postorder[pe];
	int p = find(inorder.begin() + ib, inorder.begin() + ie + 1, postorder[pe]) - inorder.begin();
	int len = p - ib;
	dfs(pb, pb + len - 1, ib, p-1, 2*root);
	dfs(pb + len, pe -1, p + 1, ie, 2*root+1);
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

postorder是后序遍历结果的数组，inorder是中序遍历结果的数组，traversal是存放二叉树每个下标的值。

dfs中，每次传入postorder的区间范围是[pb, pe]， inorder的区间为[ib, ie]，root为当前区间的根的位置。我们知道在后序遍历中，最后一个元素为二叉树的根，所以很容易获得traversal[root] = postorder[pe]，然后我们可以递归进行判断以root为根的左右子树。我们先在中序遍历数组中找到根root的值postorder[pe]所在的位置p，那么我们可以计算出左子树的节点数为len = p - ib，左子树的后序遍历数组的区间范围为[pb, pb+len-1]，中序遍历数组的区间范围为[ib, p-1]，左子树的根下标为2*root，右子树的后序遍历数组的区间范围为[pb+len, pe-1]，中序遍历数组的区间范围为[p+1, ie]，右子树的根下标为2*root+1，此时调用dfs函数进行递归即可。递归的终点为pb > pe，表示当区间不存在的时候，停止递归。

注意：这道题的n达到了30，如果开普通数组的话，长度达到了1<<30，会爆内存，所以应改成map，用多少开多少。

三、AC代码

#include<bits/stdc++.h>
using namespace std;
template<typename T=int>
T read(){
	T x;
	cin >> x;
	return x;
}

int n = read();
vector<int>postorder(n), inorder(n);
map<int,int>traversal;
void dfs( int pb, int pe, int ib, int ie, int root){
	if(pb > pe){
		return;
	}
	traversal[root] = postorder[pe];
	int p = find(inorder.begin() + ib, inorder.begin() + ie + 1, postorder[pe]) - inorder.begin();
	int len = p - ib;
	dfs(pb, pb + len - 1, ib, p-1, 2*root);
	dfs(pb + len, pe -1, p + 1, ie, 2*root+1);
}
int main(){
	for(auto &i: postorder){
		i = read();
	}
	for(auto &i: inorder){
		i = read();
	}
	dfs(0, n-1, 0, n-1, 1);
	cout << traversal[1];
	for(auto i: traversal){
		if(i.first == 1)continue;
		cout << ' ' << i.second;
	}
}
/*
Input:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Output:
4 1 6 3 5 7 2
二叉树形态：
     4
  1    6
   3  5 7
  2
按层遍历结果：
4 1 6 3 5 7 2
*/

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/99299053