L2-006 树的遍历 (25 point(s))

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

思路： 数据结构，离散数学中学到过，使用中序和后序可以还原出一个二叉树，还原的过程中核心在于，根据后续的最后一个点(根节点)与中序中的点相对应，确定中序遍历的分界线。下一步的工作就是将分出来的左右两颗子树进一步还原。也就是递归的过程，递归的出口就是中序序列，或者后续序列用完了。这里我才用了vector作为容器存储，更加方便。

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct node{
  int data;
  node * l;
  node * r;
  
};

node * create(vector<int> post, vector<int> in);
void Level(node *B, vector<int>& Le);
 
int main(){
  int n;
  cin >> n;
  vector<int> post;
  vector<int> in;
  vector<int> Le;
  
  for(int i = 0; i < n; i++){
    int t;
    cin >> t;
    post.push_back(t);
  } 
  
  for(int i = 0; i < n; i++){
    int t;
    cin >> t;
    in.push_back(t);
  }
  
  node * B = create(post,in);
  
  Level(B,Le);
  
  for(int i = 0; i < Le.size(); i++){
    if(i)cout<<" ";
    cout << Le[i];
  }
  
  
  return 0;
}
void Level(node *B, vector<int>& Le){
  queue<node*> q;
  
  if(B){
    q.push(B);
    while(!q.empty()){
      node * t = q.front();
      q.pop();
      Le.push_back(t->data);
      if(t->l){
        q.push(t->l);
      }
      
      if(t->r){
        q.push(t->r);
      }
    } 
  }
}
node * create(vector<int> post, vector<int> in){
  //出口 
  if(post.size() ==0){
    return NULL;
  }
  
  node *B = new node;
  B->data = post.back();
  
  //找到根节点 
  int m = 0;
  for(m; in[m]!=post.back();m++);
    
  //左子树 
  vector<int> p_l(post.begin(),post.begin()+m);
  vector<int> in_l(in.begin(),in.begin()+m);
  
  //右子树 
  vector<int> p_r(post.begin()+m,post.end()-1);
  vector<int> in_r(in.begin()+m+1,in.end()); 
  
  //递归执行 
  B->l = create(p_l,in_l);
  B->r = create(p_r,in_r);
  return B;
}