Привет. Статья расчитана на разработчика до мидла включительно, но в целом может оказаться полезной и другим. Так, для разминки.
Ты наверняка знаешь что такое рекурсия. Она применяется в разных местах, но, как правило, это классические графовые алгоритмы (DFS, BFS, etc.), когда надо пройтись по веткам вширь, вглубь, туда, сюда и вообще. Однако рекурсия может обойтись дорого, учитывая, помимо прочего, ограничения стека и количество данных.
Есть как минимум три относительно простые задачи, которые связаны с деревьями:
- как узнать всех родителей некоего элемента в плоском связном списке (иными словами, восстановить иерархию без построения дерева; узнать путь до элемента);
- как построить иерархическую структуру, имея на руках только плоский связный список его узлов;
- как вывернуть эту иерархию обратно в плоский связный список.
Возможно, ты удивишься, но для решения всех трёх задач рекурсия не нужна. Ниже будут их решения. Они элементарны, но неочевидны (хотя казалось бы).
(далее…)