PAT Advanced 1020 Tree Traversals（25）

题目描述：

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<iostream>
using namespace std;

int n, po[40], in[40]; //po 后序  in 中序
struct node
{
    int val;
    node*left, *right;
};
node* makenode(int h1, int t1, int h2, int t2) //两序列的首尾
{
    if(h1 > t1)    return NULL;
    node* p = new node;
    p->val = po[t1]; //后序尾元素即为根
    int index;
    for(index = h2 ; in[index] != po[t1] ; index ++); //index 即根在中序中的下标
    p->left = makenode(h1, index - 1 - h2 + h1, h2, index - 1); //两序列中子树长度相等  所以可以分别推出左子树的t1和右子树的h1
    p->right = makenode(index - h2 + h1, t1 - 1, index + 1, t2);
    return p;
}

int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i ++)   cin >> po[i];
    for(int i = 0 ; i < n ; i ++)   cin >> in[i];
    
    node* root = makenode(0, n - 1, 0, n - 1);
    node* q[40];
    int head = 0, tail = 0;
    q[tail ++] = root;
    while(head < tail)
    {
        if(head != 0)   cout << ' ';
        node* p = q[head ++]; // 出队
        cout << p->val;
        if(p->left)   q[tail ++] = p->left; // 入队
        if(p->right)  q[tail ++] = p->right;
    }
    return 0;
}