PAT甲级1020 Tree Traversals：[C++题解]树的遍历、由中序序列和后序序列递归建树

本文主要是介绍PAT甲级1020 Tree Traversals：[C++题解]树的遍历、由中序序列和后序序列递归建树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 题目分析
- 题目链接

题目分析

在这里插入图片描述
题意重述：给定一棵二叉树的后序遍历序列和中序遍历序列，让求层次遍历的序列。

分析：

后序遍历：先左子树、右子树，最后再遍历根结点。

中序遍历：先左子树，再根结点，然后是右子树。

给定中序序列和后续序列，便可以唯一确定这棵二叉树的形状。

由于后序遍历最后遍历根结点，所以最后一个就是根结点。找到根结点的值，我们就可以在中序序列中找到根结点，从而把中序序列分成左子树、根结点、右子树三部分。这三部分也可以在后序序列中找到对应的部分。

然后对于后序序列的各个部分，递归上面这个过程，先找到这个部分的根结点，再对应到中序序列，把中序序列的这一部分再分成左子树、根结点、右子树三部分……

这里需要用到hash表l和r，分别用来存一个结点的左儿子和右儿子。这样查找某结点是否存在儿子，就方便很多。
ac代码

#include<bits/stdc++.h>
using namespace std;const int N =40;int n;
int postOrder[N], inOrder[N];unordered_map<int,int> l,r,pos; //l和r存左右儿子,pos存中序遍历每个值的下标
int q[N];/*build函数：根据中序序列和后序序列建树，返回树根il：中序序列左端点；ir：中序序列右端点pl:后序序列左端点；pr：后序序列右端点
*/
int  build(int il, int ir, int pl ,int pr){int root = postOrder[pr];  //在后序序列中找到根结点的值，存在root中int k =pos[root];// 根结点在中序序列中的位置//看中序序列//中序序列中存在左子树if(il < k){//左子树的树根 就是 root的左儿子l[root] = build(il,k-1, pl,pl+(k-1-il));}//中序序列中存在右子树if(k<ir){//右子树的树根就是root的右儿子r[root] = build(k+1,ir,pl+(k-1-il)+1,pr-1);}return root; //返回树根
}
/*
bfs:层次遍历
手写队列*/
void bfs(int root){int hh =0 ,tt =0;q[0] =root;  //q[0]为根结点while(hh<=tt){ //队列不空int t =q[hh++]; //取队首元素//左子树存在，左子树的树根加入队列if(l.count(t)) q[++tt] =l[t];  //左儿子存在加入队列//右子树存在，右子树的树根加入队列if(r.count(t)) q[++tt] =r[t]; //右儿子存在加入队列}cout<<q[0];for(int i=1;i<n;i++) cout<<" "<<q[i];
}int main(){cin>> n;for(int i=0; i<n;i++) cin>> postOrder[i];for(int i=0;i<n;i++){cin>>inOrder[i];pos[inOrder[i]] =i; //记录每个值在中序序列中的位置}int root = build(0,n-1,0,n-1);bfs(root);}