美团笔试第3题

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <map>
using namespace std;

struct Node
{
    char val;
    Node * left;
    Node * right;
    Node(){val = 0;left=nullptr;right=nullptr;}
    Node(int x){val = x;left=nullptr;right=nullptr;}
};

// 全局定义
unordered_map<int, Node*> umap; // 序号+指针
unordered_map<Node*, int> rmap; // 指针+子树的结果

Node* build(vector<int> data, string str){
    Node* head = new(Node);
    head->val = str[0];
    umap[0] = head;
    rmap[head] = 0;
    for (int i = 0; i < data.size(); i++)
    {
        int index = i+1;
        // 找到头结点
        Node* cur = umap[data[i]-1];
        // 建立一个节点
        Node* nn = new(Node);
        nn->val = str[index];
        if(cur->left == nullptr){
            cur->left = nn;
            umap[index] = cur->left;
            rmap[cur->left] = 0;
        }
        else{
            cur->right = nn;
            umap[index] = cur->right;
            rmap[cur->right] = 0;
        }
    }
    return head;
    
}


map<char, Node*> readNode(Node* head){
    map<char, Node*> smap;  // 树下的map用来求数量
    if(head == nullptr)
        return smap;
    map<char, Node*> rl = readNode(head->left);
    map<char, Node*> rr = readNode(head->right);
    smap[head->val] = head;
    smap.insert(rl.begin(), rl.end());
    smap.insert(rr.begin(), rr.end());
    rmap[head] = smap.size();
}

int main(){
    int a;
    cin>>a;
    int b = a;
    vector<int> sdata;
    while (--a)
    {
        int x;
        cin>>x;
        sdata.push_back(x);
    }
    string str;
    cin>>str;

    // 构建二叉树
    Node* head = build(sdata, str);

    // 遍历节点
    auto rs = readNode(head);

    //  输出
    for (int i = 0; i < umap.size(); i++)
    {
        Node* cur = umap[i];
        if (i<umap.size()-1)
            cout<<rmap[cur]<<" ";
        else
            cout<<rmap[cur];
    }

    return 0;

}

/* 样例
6
1 2 2 1 4
ABCCAD

*/