C++のmapで親ノードを取得する方法
解決したいこと
解決したいこと）
C++のmapで親ノードを取得する方法
具体的な問題
//n個の値が入力されます。これらの値を二分探索木にぶち込みます。後ろのn-1個の値の親ノードの値を出力せよ。そしてmapで実現せよ。
一行目は入力される値の数
二行目は入力される値の列
//input
5
3 1 5 2 4
1(3)
/ \
2(1) 3(5)
\ /
4(2) 5(4)
//output
3 3 1 5
普通の二分探索木での実現
#include<iostream>
using namespace std;
struct Node {
int value;
Node* left, * right;
};
Node* Insert(Node* node, int value, int father) {
if (node == NULL) {
node = new Node;
if(father != -1) cout << father << endl;
node->value = value;
node->left = node->right = NULL;
}
if (value < node->value) {
node->left = Insert(node->left, value, node->value);
}
else if (value > node->value) {
node->right = Insert(node->right, value, node->value);
}
return node;
}
int main()
{
int n, number;
while (cin >> n) {
Node* T = NULL;
for (int i = 0; i < n; i++) {
cin >> number;
T = Insert(T, number, -1);
}
}
return 0;
}
データ制限:
2≤n≤5×10^4
1≤ni≤2×10^9
時間制限：1s
データ制限：64MB
//小さいデータはこの方法でOKです、ただ仮にnが50000と大きい場合はTLEになります。
現在わかっていること
普通の二分探索木だとTLEになってしまいますので、赤黒木ベースのmapで実現する必要があります（←というヒントをもらってます、ただ使わなくてもよい）。
mapにデータをぶち込んでから、どうやってmapの中で親ノード値をゲットするのかわかりません。T T
0
