Проблема в том, что вы добавляете новые члены в m2
, когда root
виден сверху дерева:
if(m1.find(m2[root]+1)==m1.end())
{
m2[root->right]=m2[root]+1;
Это не будет работать для такого тестового примера
1
10
1 2 L 1 5 R 2 -1 N 2 3 R 5 -1 N 5 -1 N 3 -1 N 3 4 R 4 -1 N 4 6 R
, который имеет следующее дерево:
1
/ \
2 5
\
3
\
4
\
6
Ожидаемый результат будет
2 1 5 6
, но ваш код приведет к
2 1 5
Здесь, когда root
является узлом 2, узел 3 будет добавлен к m2
. Но когда узел 3 root
, он не добавит узел 4 к m2
, поскольку узел 3 не может быть виден сверху и, следовательно, не инициализирует его правильно в положение 1
.
Впоследствии, когда root
установлен на узел 4, он будет искать его в m2
. Но поскольку этот ключ еще не существует, он создаст новое значение с помощью стандартного конструктора int (0
). Из-за этого ваш код предполагает, что узел 6 находится в позиции 1
, которая уже затмевается узлом 5.
Однако исправить это просто. Просто переместите присвоения m2
из if-clauses:
m2[root->left]=m2[root]-1;
if(m1.find(m2[root]-1)==m1.end())
{
m1[m2[root]-1]=root->left->data;
}
То же самое для правого случая.