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 4 7 8 5 3 6
• 中序序列为：7 4 8 2 5 1 3 6
• 后序序列为：7 8 4 5 2 6 3 1

后序和先序遍历提供根节点位置，然后再中序序列中区分出左子树和右子树，递归建树，然后BFS层序遍历。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int post[50],in[50];

struct node{
    int data;
    node* lchild;
    node* rchild;
};

node* creatTree(int postL,int postR,int inL,int inR){
    if(postL > postR) return NULL;
    int k;
    for(k = inL;k<=inR;k++){
        if(in[k]==post[postR]) break;
    }
    int numLeft = k - inL;
    node* root = new node;
    root->data = post[postR];
    root->lchild = creatTree(postL,postL+numLeft-1,inL,k-1);
    root->rchild = creatTree(postL+numLeft,postR-1,k+1,inR);
    return root;
}

int num = 0;
int n;
void BFS(node* root){
    queue<node*> q;
    q.push(root);
    while(!q.empty()){
        node* now = q.front();
        printf("%d",now->data);
        num++;
        if(num<n) printf(" ");
        q.pop();
        if(now->lchild!=NULL) q.push(now->lchild);
        if(now->rchild!=NULL) q.push(now->rchild);
    }
    return ;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&post[i]);
    }
    for(int i=0;i<n;i++){
        scanf("%d",&in[i]);
    }
    node* root = creatTree(0,n-1,0,n-1);
    BFS(root);
}

参考

用latex画二叉树

\documentclass{article}
\usepackage{tikz-qtree}
\begin{document}
\tikzset{every tree node/.style={minimum width=3em,draw,circle},
         blank/.style={draw=none},
         edge from parent/.style=
         {draw,edge from parent path={(\tikzparentnode) -- (\tikzchildnode)}},
         level distance=1.5cm}
\begin{tikzpicture}
\Tree
[.1
    [.2
        \edge[];[.4
            \edge[]; {7}
            \edge[]; {8}
        ]
        \edge[]; {5}
    ]
    [.3
        \edge[blank]; \node[blank]{};
        \edge[]; {6}
    ]
]
\end{tikzpicture}
\end{document}