photoshop制作网站,和男朋友都是第一次做网站,上传文件到网站根目录,新乡电商网站建设题目链接#xff1a;https://pintia.cn/problem-sets/994805046380707840/problems/994805069361299456 题意#xff1a;给出一个二叉树的结点数目n#xff0c;后序遍历序列post#xff0c;中序遍历序列in#xff0c;求其层序遍历序列。 思路#xff1a;首先给二叉树每个…题目链接https://pintia.cn/problem-sets/994805046380707840/problems/994805069361299456 题意给出一个二叉树的结点数目n后序遍历序列post中序遍历序列in求其层序遍历序列。 思路首先给二叉树每个结点一个编号按照层序遍历的顺序一次编号即一个编号为i的结点其左子树根节点编号为2*i1其右子树根节点的编号为2*i2二叉树的根节点为0因为30层的二叉树编号达到了2*30-1不能直接用数组存会爆空间。我们可以用优先队列和二元组pair来存pair的first存结点编号second存该结点的值。之后就暴力递归了每次将根节点入队然后依次对其左子树、右子树递归调用。 AC代码 #includebits/stdc.h
using namespace std;int post[35],in[35];
int n;
typedef pairint,int PII;
priority_queuePII,vectorPII,greaterPII pq;void getc(int l,int r,int root,int index){if(lr) return;int il;while(in[i]!post[root]) i;pq.push(make_pair(index,post[root]));getc(l,i-1,root-1-ri,2*index1);getc(i1,r,root-1,2*index2);
}int main(){scanf(%d,n);for(int i0;in;i)scanf(%d,post[i]);for(int i0;in;i)scanf(%d,in[i]);getc(0,n-1,n-1,0);PII ppq.top();pq.pop();printf(%d,p.second);while(!pq.empty()){ppq.top();pq.pop();printf( %d,p.second);}printf(\n);return 0;
} 转载于:https://www.cnblogs.com/FrankChen831X/p/10542561.html
