首页 > 代码库 > PAT甲题题解-1127. ZigZagging on a Tree (30)-中序、后序建树
PAT甲题题解-1127. ZigZagging on a Tree (30)-中序、后序建树
根据中序遍历和前序遍历确定一棵二叉树,然后按“层次遍历”序列输出。
输出规则:除根节点外,接下来每层的节点输出顺序是:先从左到右,再从右到左,交替输出
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <string> #include <map> #define LEFT 0 #define RIGHT 1 using namespace std; const int maxn=35; int inorder[maxn]; int postorder[maxn]; int level[maxn][maxn]; //每层的节点id int levelcnt[maxn]; //每层的节点个数 int maxlayer=0; int cnt=0; //节点id struct Node{ int left=-1,right=-1; int val; }node[maxn]; //根据中序遍历和后序遍历建立树 void build(int inL,int inR,int postL,int postR,int fa,int LorR){ if(inL>inR) return; int val=postorder[postR]; int idx; //在中序遍历中找出父亲节点的索引,其左边是左子树,右边是右子树 for(int i=inL;i<=inR;i++){ if(inorder[i]==val){ idx=i; break; } } int lnum=idx-inL; cnt++; node[cnt].val=val; if(LorR==LEFT) node[fa].left=cnt; else if(LorR==RIGHT) node[fa].right=cnt; int tmp=cnt; build(inL,idx-1,postL,postL+lnum-1,tmp,LEFT); build(idx+1,inR,postL+lnum,postR-1,tmp,RIGHT); } void dfs(int root,int layer){ if(root==-1) return; maxlayer=max(layer,maxlayer); level[layer][levelcnt[layer]]=root; levelcnt[layer]++; dfs(node[root].left,layer+1); dfs(node[root].right,layer+1); } int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>inorder[i]; for(int i=1;i<=n;i++) cin>>postorder[i]; build(1,n,1,n,-1,-1); dfs(1,1); bool flag=true; printf("%d",node[1].val); for(int i=2;i<=maxlayer;i++){ if(flag){ for(int j=0;j<levelcnt[i];j++) printf(" %d",node[level[i][j]].val); } else{ for(int j=levelcnt[i]-1;j>=0;j--) printf(" %d",node[level[i][j]].val); } flag=!flag; } return 0; }
PAT甲题题解-1127. ZigZagging on a Tree (30)-中序、后序建树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。