7-3 Left-View of Binary Tree (25分)

The left-view of a binary tree is a list of nodes obtained by looking at the tree from left hand side and from top down. For example, given a tree shown by the figure, its left-view is { 1, 2, 3, 4, 5 }

Given the inorder and preorder traversal sequences of a binary tree, you are supposed to output its left-view.
Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤20), which is the total number of nodes in the tree. Then given in the following 2 lines are the inorder and preorder traversal sequences of the tree, respectively. All the keys in the tree are distinct positive integers in the range of int.
Output Specification:

For each case, print in a line the left-view of the tree. All the numbers in a line are separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

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

Sample Output:

1 2 3 4 5

大概的题意是给一个二叉树的权值的中序和前序遍历，还原二叉树，然后输出它的左视图（其实也就是层序遍历的每层的第一个节点）
AC代码

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
const int N=30;

int pre[N],in[N];
int n,q[N];
vector<int>left_view;
unordered_map<int,int>pos,l,r;

int build(int il,int ir,int pl,int pr)
{
    int root=pre[pl];
    int k=pos[root];
    if(k>il)l[root]=build(il,k-1,pl+1,pl+1+k-1-il);
    if(k<ir)r[root]=build(k+1,ir,pr-ir+k+1,pr);

    return root;
}

void bfs(int root)
{
    int hh=0,tt=0;
    q[0]=root;
    while(hh<=tt)
    {
        int head=hh,tail=tt;
        while(hh<=tail)
        {
            int t=q[hh++];
            if(l.count(t))q[++tt]=l[t];
            if(r.count(t))q[++tt]=r[t];
        }
        left_view.push_back(q[head]);
    }

}

int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>in[i];
        pos[in[i]]=i;
    }
    for(int i=0;i<n;++i)cin>>pre[i];

    int root=build(0,n-1,0,n-1);
    bfs(root);
    cout<<root;
    for(int i=1;i<left_view.size();++i)cout<<' '<<left_view[i];

    return 0;
}