美团笔试第3题
美图第三题，用map来访问子树，并合并，map大小就是不重复字母总数。
#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
*/
