PAT甲级：1174 Left-View of Binary Tree

题目：1174 Left-View of Binary Tree　　25分

题解：层次遍历输出每一行最左边的元素。(最开始以为输出部分节点的左子树...想不到思路)

using namespace std;
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cctype>
#include <climits>
#include <set>
#include <stack>
#include <cstring>
#include <sstream>
#include <unordered_map>


// 从上到下输出每一行最左边那个结点
vector<int> in,pre,ans;
map<int,int> pos,mp;
int Tree[25][2],root;
struct node{
    int nodeid,level;
};
void deal(int &idx,int i0,int i1,int p0,int p1){
    if(i0>i1){
        return;
    }
    idx = p0;
    int i = pos[pre[p0]];
    int Llen = i - i0;
    deal(Tree[idx][0],i0,i-1,p0+1,p0+Llen);
    deal(Tree[idx][1],i+1,i1,p0+1+Llen,p1);
}
void bfs(){
    queue<node> q;
    q.push(node{root,1});
    while(!q.empty()){
        node t = q.front();
        // cout << "level: " << pre[t.nodeid] << endl;
        q.pop();
        int tl = t.level;
        if(mp.find(tl) == mp.end()){
            ans.push_back(t.nodeid);
            mp[tl] ++;
        }
        int lid = Tree[t.nodeid][0],rid = Tree[t.nodeid][1];
        if(lid){
            q.push(node{lid,t.level+1});
        }
        if(rid){
            q.push(node{rid,t.level+1});
        }
    }
}
void ex1174(){
    int n;cin >> n;
    in.resize(n+1);
    pre.resize(n+1);
    for(int i=1;i<=n;i++){
        cin >> in[i];
        pos[in[i]] = i;
    }
    for(int i=1;i<=n;i++){
        cin >> pre[i];      
    }
    deal(root,1,n,1,n);
    bfs();
    for(int i=0;i<ans.size();i++){
        cout << pre[ans[i]];
        if(i+1 != ans.size()){
            cout << " ";
        }
    }
}

int main(){
    ex1174();

    return 0;
}