1127 ZigZagging on a Tree (30 分)树的层次遍历
1127 ZigZagging on a Tree (30 分)
Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However,if you think the problem is too simple,then you are too naive. This time you are supposed to print the numbers in "zigzagging order" -- that is,starting from the root,print the numbers level-by-level,alternating between left to right and right to left. For example,for the following tree you must output: 1 11 5 8 17 12 20 15. Input Specification:Each input file contains one test case. For each case,the first line gives a positive integer N (≤30),the total number of nodes in the binary tree. The second line gives the inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space. Output Specification:For each test case,print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space,and there must be no extra space at the end of the line. Sample Input:8 12 11 20 17 1 15 8 5 12 20 17 11 15 8 5 1 Sample Output:
#include<iostream> #include<vector> #include<algorithm> #include<queue> #include<string> #include<map> #include<set> using namespace std; bool flag=true; vector<int> path; //对树进行深度遍历 struct Node { int data; Node *lchild,*rchild; }; //Node *tree=nullptr; void create(int in[],int il,int ir,int po[],int pl,int pr,Node* &root) { if(root==nullptr) { root=new Node; root->data=po[pr]; root->lchild=root->rchild=nullptr; } int i=0; while(in[i]!=po[pr]) i++; int len=i-il;//减去中心点坐标才对 int rlen=ir-i; if(len>0) create(in,il,il+len-1,po,pl,pl+len-1,root->lchild); if(rlen>0) create(in,il+len+1,ir,pl+len,pr-1,root->rchild); } void print(Node *tree) { if(tree) { print(tree->lchild); cout<<tree->data<<endl; print(tree->rchild); } } void level(Node *tree,int n) { vector<int> print; int front=0; int rail=0; Node* queue[n+10]; int odd=1; queue[rail++]=tree; cout<<tree->data; //print.push_back(tree->data); //front++; int last=1; while(front<rail) { //cout<<print.size()<<endl; Node *temp=queue[front++]; //cout<<temp->data<<endl; //rail++; if(temp->lchild!=nullptr) { queue[rail++]=temp->lchild; if(temp->lchild) print.push_back(temp->lchild->data); } if(temp->rchild!=nullptr) { queue[rail++]=temp->rchild; if(temp->rchild) print.push_back(temp->rchild->data); } if(front==last) { last=rail; if(odd==2) { reverse(print.begin(),print.end()); odd=1; } else odd=2; for(auto num:print) cout<<" "<<num; print.clear(); } } } int main() { int n; cin>>n; int in[n]; int po[n]; for(int i=0;i<n;i++) cin>>in[i]; for(int j=0;j<n;j++) cin>>po[j]; Node* tree=nullptr; create(in,0,n-1,n-1,tree); //print(tree); level(tree,n); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |