题目:http://pat.zju.edu.cn/contests/pat-a-practise/1020
题解:
题意就是给一个二叉树的后序和中序,然后确定这棵二叉树,然后层序输出这棵树。
主要思路就是通过后序去确定根root,因为后序中根root肯定是在最后一个的,然后通过找到的根root去把中序的划分成两部分,左边的是根root的左子树,右边的是根root的右子树,再递归左子树和右子树。最终确定二叉树的逻辑结构。
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<string> #include<vector> #include<queue> #include<algorithm> using namespace std; struct point { int left,right; }num[35]; queue<int> q; vector<int> ans; int buildTree(int a[],int b[],int n) { if(n<=0) return -1; int root=a[n-1]; num[root].left=-1; num[root].right=-1; int i; for(i=0;i<n;++i) if(b[i]==a[n-1]) break; num[root].left=buildTree(a,b,i); num[root].right=buildTree(a+i,b+i+1,n-i-1); return root; } void levelTree(int idx) { int temp; q.push(idx); for(;!q.empty();) { temp=q.front(); q.pop(); if(num[temp].left!=-1) q.push(num[temp].left); if(num[temp].right!=-1) q.push(num[temp].right); ans.push_back(temp); } } int main() { int n; int a[35],b[35]; scanf("%d",&n); for(int i=0;i<n;++i) scanf("%d",a+i); for(int i=0;i<n;++i) scanf("%d",b+i); int root=buildTree(a,b,n); levelTree(root); printf("%d",ans[0]); for(int i=1;i<ans.size();++i) printf(" %d",ans[i]); printf("\n"); return 0; }