【题解-Acwing】1497. 树的遍历

题目1497. 树的遍历题目描述一个二叉树树中每个节点的权值互不相同。现在给出它的后序遍历和中序遍历请你输出它的层序遍历。输入第一行包含整数 N表示二叉树的节点数。第二行包含 N 个整数表示二叉树的后序遍历。第三行包含 N 个整数表示二叉树的中序遍历。输出输出一行 N 个整数表示二叉树的层序遍历。数据范围1≤N≤30,官方并未给出各节点权值的取值范围为方便起见在本网站范围取为 1∼N。时空限制1s / 64MB输入样例7 2 3 1 5 7 6 4 1 2 3 4 5 6 7输出样例4 1 6 3 5 7 2代码#includebits/stdc.husingnamespacestd;constintN3010;intn,postorder[N],inorder[N];unordered_mapint,intpos,l,r;boolvis[N];//pos是中序遍历序列中每个元素的下标//l是左子树//r是右子树intbuild(intpl,intpr,intil,intir){introotpostorder[pr];intmpos[root];if(ilm)l[root]build(pl,plm-1-il,il,m-1);if(mir)r[root]build(plm-il,pr-1,m1,ir);returnroot;}voidbfs(intsx){queueintq;q.push(sx);vis[sx]true;coutsx ;while(!q.empty()){inttq.front();q.pop();if(l.count(t)!vis[l[t]]){q.push(l[t]);vis[l[t]]true;coutl[t] ;}if(r.count(t)!vis[r[t]]){q.push(r[t]);vis[r[t]]true;coutr[t] ;}}}intmain(){cinn;for(inti0;in;i)cinpostorder[i];for(inti0;in;i){cininorder[i];pos[inorder[i]]i;}introotbuild(0,n-1,0,n-1);bfs(root);return0;}结果