北京网站设计推荐柚米,制作论坛做网站,石家庄模板建站系统,建设工程合同在性质上属于假设一个二叉树上各结点的权值互不相同。
我们就可以通过其后序遍历和中序遍历来确定唯一二叉树。
请你输出该二叉树的 ZZ 字形遍历序列----也就是说#xff0c;从根结点开始#xff0c;逐层遍历#xff0c;第一层从右到左遍历#xff0c;第二层从左到右遍历#xff0c;…假设一个二叉树上各结点的权值互不相同。
我们就可以通过其后序遍历和中序遍历来确定唯一二叉树。
请你输出该二叉树的 ZZ 字形遍历序列----也就是说从根结点开始逐层遍历第一层从右到左遍历第二层从左到右遍历第三层从右到左遍历以此类推。
例如下图所示二叉树其 ZZ 字形遍历序列应该为1 11 5 8 17 12 20 15。 输入格式
第一行包含整数 NN表示二叉树结点数量。
第二行包含 NN 个整数表示二叉树的中序遍历序列。
第三行包含 NN 个整数表示二叉树的后序遍历序列。
输出格式
输出二叉树的 ZZ 字形遍历序列。
数据范围
1≤N≤301≤N≤30
输入样例
8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1输出样例
1 11 5 8 17 12 20 15
#include iostream
#include cstring
#include map
#include queue
#include algorithm
#include vector
using namespace std;
const int N40;
int inorder[N],postorder[N];
int n;
int depth[N];
mapint,intl,r,pos; vectorintres;
int build(int il,int ir,int pl,int pr)
{if(ilir) return 0 ;int rootpostorder[pr]; int kpos[root];if(ilk) l[root]build(il,k-1,pl,plk-1-il); if(irk) r[root]build(k1,ir,plk-il,pr-1);// coutroot l[root] r[root]endl;return root;
}void bfs(int root)
{ queueintq;q.push(root);int st1;int flag0;while(!q.empty()){int sizeq.size();for(int i0;isize;i){auto tq.front();res.push_back(t);q.pop();if(l[t]) q.push(l[t]);if(r[t]) q.push(r[t]);}if(!flag) reverse(res.begin()res.size()-size,res.end());flag!flag;}
}
int main()
{cinn;// memset(l,-1,sizeof(l));// memset(r,-1,sizeof(r));for(int i0;in;i) cininorder[i],pos[inorder[i]]i;for(int i0;in;i) cinpostorder[i];int root build(0,n-1,0,n-1);bfs(root);// int rootpostorder[n-1];coutres[0];for(int i1;in;i) cout res[i];
}
