PAT1020

　　最近在刷PAT题，将自己的解题过程和代码写在blog上。

Tree Traversals (25)

时间限制

400 ms

内存限制

32000 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

这题自己想了挺久，根据后序排列和中序排列的数组来确定一棵二叉树。解题思路：根据后序排列可以确定树的根，根据中序排列可以比对根节点确定左右子树。然后因为后序排列安照左-》右-》根的顺序遍历，而中序排列按照左->根->右的顺序，可以

确定后序排列中的从左到右直到达到根节点左边的肯定为左子树；即不断确定根节点，左右子树来完善这颗树。

　　当树行成后需要按层级打印，这里注意不是按照先序遍历的方式打印，这时需要用到队列，将根元素先入队，再将左右子树节点入队，根据节点不为空的原则进行出队操作，一直到队列为空；

  1 //
  2 //  main.cpp
  3 //  1020
  4 //
  5 //  Created by apple on 14-2-13.
  6 //  Copyright (c) 2014年 apple. All rights reserved.
  7 //
  8 
  9 #include <iostream>
 10 #include <queue>
 11 using namespace std;
 12 #define  MAX 31
 13 int inorder[MAX];
 14 int postorder[MAX];
 15 typedef struct Node{
 16     int value;
 17     struct Node *lchild;
 18     struct Node *rchlid;
 19 }Node;
 20 
 21 void LevelTravel(Node *root);
 22 Node *createtree(int istart,int iend,int pstart,int pend)
 23 {
 24     int i,j;
 25     Node *node = new Node();
 26     
 27     node->lchild = NULL;
 28     node->rchlid = NULL;
 29     node->value = postorder[pend];
 30     if (istart>iend || pstart>pend)
 31     {
 32         return NULL;
 33     }
 34     
 35 
 36     for(i = istart,j = pstart; i < iend && j < pend; i++,j++)
 37     {
 38         if (inorder[i] == postorder[pend])
 39         {
 40             break;
 41         }
 42     }
 43     
 44     
 45     node->lchild = createtree(istart,i-1,pstart,j-1);
 46     node->rchlid = createtree(i+1,iend,j,pend-1);
 47     
 48     
 49     return node;
 50 }
 51 
 52 
 53 
 54 int main()
 55 {
 56     int i;
 57     int num;
 58     cin>>num;
 59     for (i = 0; i<num; i++)
 60     {
 61         cin>>postorder[i];
 62     }
 63     
 64     for (i = 0; i<num; i++)
 65     {
 66         cin>>inorder[i];
 67     }
 68     
 69     Node *root = NULL;
 70     root = createtree(0,num-1,0,num-1);
 71     
 72    LevelTravel(root);
 73     
 74     return 0;
 75 }
 76 
 77 void LevelTravel(Node *root)
 78 {
 79     queue<Node*>q;
 80     if (root!=NULL)
 81     {
 82         printf("%d",root->value);
 83         if(root->lchild!=NULL)q.push(root->lchild);
 84         if(root->rchlid!=NULL)q.push(root->rchlid);
 85     }
 86     else
 87         return;
 88     while(!q.empty())
 89     {
 90         Node *node = q.front();
 91         
 92         if (node == NULL)
 93         {
 94             continue;
 95         }
 96                 q.pop();
 97         printf(" %d",node->value);
 98     
 99         if(node->lchild!=NULL) q.push(node->lchild);
100         
101         if(node->rchlid!=NULL) q.push(node->rchlid);
102         
103     }
104     printf("
");
105     
106 }