Это не домашнее задание, и мне не нужно отвечать на него, но теперь я стал одержим:)
Проблема заключается в следующем:
- Создайте алгоритм для деструктивного сглаживания двоичного дерева в связанном списке, в ширину. Хорошо, достаточно легко. Просто создайте очередь и сделайте то, что вам нужно.
- Это была разминка. Теперь реализуйте его с постоянным хранилищем (рекурсия, если вы можете найти ответ с ее помощью, является логарифмическим хранилищем, а не константой).
Я нашел решение этой проблемы в Интернете около года назад, но теперь я забыл об этом, и я хочу знать:)
Трюк, насколько я помню, включал использование дерева для реализации очереди, используя деструктивный характер алгоритма. Когда вы связываете список, вы также нажимаете элемент в очередь.
Каждый раз, когда я пытаюсь решить эту проблему, я теряю узлы (например, каждый раз, когда я связываю следующий node/add в очередь), мне требуется дополнительное хранилище, или я не могу определить запутанный метод, который мне нужен чтобы вернуться к node, у которого есть указатель, который мне нужен.
Даже ссылка на эту оригинальную статью/сообщение была бы полезной для меня:) Google не дает мне радости.
Edit:
Jérémie указала, что существует довольно простой (и хорошо известный ответ), если у вас есть родительский указатель. Хотя теперь я думаю, что он прав относительно исходного решения, содержащего родительский указатель, я действительно хотел решить проблему без него:)
Уточненные требования используют это определение для node:
struct tree_node
{
int value;
tree_node* left;
tree_node* right;
};