Основная идея аналогична алгоритму инверсии списка, с одним сверхъестественным хитрым взломом (с теоретической точки зрения, вероятно, обманом), основанным на том факте, что указатели (на всех языках, которые в настоящее время известны людям) , 0 режим 4 как целые числа.
Идея состоит в том, что вы можете щелкнуть указателями на пути вниз по дереву, чтобы указывать вверх. Проблема в том, что - и именно здесь вы отклоняетесь от алгоритма инверсии списка - когда вы
для возврата нужно знать, указывает ли левый верх или правый верх; в этот момент мы используем взломать.
Псевдокод следует:
current = root->left
next = current
while (current != null) {
next = current->left
current->left = static_cast<int>(prev) + 1 // ugly hack.
current = next
}
status = done
while (current != root or status != done) {
if (status = done) {
if (static_cast<u32>(current->left) %4 = 1) {
next = static_cast<u32>(current->left) -1
current->left = prev
status = middle
}
else {
next = current->right
current->right = prev
status = done
}
prev = current
current = next
}
else if (status == left) {
if (current->left) {
prev = current->left
current->left = static_cast<u32>(next) +1
next = current
}
else
status = middle
}
else if (status == right) {
if (current->right) {
prev = current->right;
current ->right = next;
next = current
}
else
status = done
}
else {// status == middle
work_on_node(current)
status = right
}
}