// 1020_Tree Traversals.cpp : 定义控制台应用程序的入口点。//1020. Tree Traversals (25)////时间限制//400 ms//内存限制//65536 kB//代码长度限制//16000 B//判题程序//Standard//作者//CHEN, Yue//Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.////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 postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.////Output Specification:////For each test case, PRint in one line the level order traversal sequence of the corresponding binary tree. 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://7//2 3 1 5 7 6 4//1 2 3 4 5 6 7//Sample Output://4 1 6 3 5 7 2#include "stdafx.h"#include "stdio.h"#include "iostream"#include "string.h"#include "stdlib.h"#include "string"#include "algorithm"#include "queue"using namespace std;typedef struct node{ int value; struct node *lchild; struct node *rchild;}node;int post[32],in[32];node *create(int pl,int pr,int il,int ir){ if(pl>pr) return NULL; int t = il; while(in[t]!=post[pr]) t++; node *binode= (node *)malloc(sizeof(node)); binode->value = post[pr]; binode->lchild = create(pl,pl+t-il-1,il,t-1); binode->rchild = create(pl+t-il,pr-1,t+1,ir); return binode;}void bfs(node *root){ queue<node *>q; //队列元素用结构体指针 node *temp =NULL; q.push(root); bool first = true; while(!q.empty()){ temp = q.front(); q.pop(); if(temp){ if(first){ cout<<temp->value; first = false; } else{ cout<<" "<<temp->value; } q.push(temp->lchild); q.push(temp->rchild); } } cout<<endl;}int main(){ int n; while(cin>>n){ for(int i =0;i<n;i++) cin>>post[i]; for(int i =0;i<n;i++) cin>>in[i]; node *root; root = create(0,n-1,0,n-1); bfs(root); } return 0;}
