距离18号的PAT考试还有18天,最重要的是挖透做过的每一题
(1)基本思路:
1.建树用right数组和left保存各个节点的右左节点
2.层次遍历
#include#include #include using namespace std;#define M 32int post[M];int in[M];int n;int left[M];int right[M];queue q;//建树int built_tree(int st1,int end1,int st2,int end2,int root){ if(st1 > end1 || st2 > end2) return 0; if(st1 == end1 || st2 == end2) return post[st1]; for(int i=st2;i<=end2;i++) { if(root == in[i]) { int ne1=st1+i-st2-1; left[root]=built_tree(st1,ne1,st2,i-1,post[ne1]); right[root]=built_tree(ne1+1,end1-1,i+1,end2,post[end1-1]); } } return root;}int main() { scanf("%d",&n); memset(post,0,sizeof(post)); memset(in,0,sizeof(in)); memset(left,0,sizeof(left)); memset(right,0,sizeof(right)); for(int i=0;i
(2)不建树直接用一个数组存储结果
不过在这之前先试一下更简单的---转换成先序(根左右)
#include#include #include using namespace std;#define M 32int post[M];int in[M];int n;//start 为in中的start end同,root为post中的rootvoid pre(int root,int start,int end,int cnt) { if(start > end) return; //find left subtree and right subtree //比如左子树不存在那么该算法会认为根为左子树的start而end则是通过根减一得到 //所以会产生start比end大的情况 //同理右子树不存在start为i+1而新的end为原来的end //如果是一个节点的树那么会有start=end //如果start end相等就是多个节点的树 int i; for(i=start;i<=end;i++) { if(in[i]==post[root]) break; } cnt == 0? printf("%d",post[root]):printf(" %d",post[root]); //left subtree pre(root-end+i-1,start,i-1,++cnt); //right subtree pre(root-1,i+1,end,++cnt);}int main() { scanf("%d",&n); memset(post,0,sizeof(post)); memset(in,0,sizeof(in)); for(int i=0;i
层次遍历
技巧就是虽然不是层次遍历但是可以用index来得到对应的层次中的节点
1
| |
2 3
| | | |
4 5 6 7
访问顺序虽然是1 2 4 5 3 6 7 (先序)
但是用index从零开始记录
访问顺序虽然没有变但是存在数组的位置却是按照层次来的 比如0位置存1 2*0+1位置 存2 2*0+2存3以后同理
#include#include using namespace std;#define M 32//数组开大一点不然最后一个过不去#define N 1000000int post[M];int in[M];//不能只开M的大小的数组因为空节点也会存在level中int level[N];int n;void pre(int root,int start,int end,int index) { if(start > end) return; int i; for(i=start;i<=end;i++) { if(in[i]==post[root]) break; } level[index]=post[root]; //left subtree pre(root-end+i-1,start,i-1,2*index+1); //right subtree pre(root-1,i+1,end,2*index+2);}int main() { scanf("%d",&n); memset(post,0,sizeof(post)); memset(in,0,sizeof(in)); memset(level,-1,sizeof(level)); for(int i=0;i
