Дано n-ary tree, нужно написать preorder обход дерева в глубину.
В этой задачке будет много терминов. Предполагая, что они не сами собой разумеющиеся, я попробую их сперва описать.
Двоичное (бинарное) дерево — у каждого узла два ребёнка. Троичное — три, ну и N-чное — общий случай, когда количество детей любое.
N-ary Tree
Есть различные варианты обхода дерева в глубину: preorder, inorder, postorder.
В данной задаче требуется написать preorder, поэтому необходимо знать в чём отличия разных вариантов обхода.
Обычно работают с двоичными деревьями, тогда алгоритм описывается так:
Т.к. у нас N детей в общем случае, то алгоритм немного меняется — идём рекурсивно слева направо во все поддеревья (сперва в левое, а потом в правое — частный случай).
На простом примере:
Вернуть нужно [1,3,5,6,2,4].
Печатаем 1, идём в 3. Печатаем 3, идём в 5. Дальше некуда идти, стек рекурсивных вызовов начинает разматываться, возвращаемся в 3, идём в 6 (продолжаем рекурсивный обход детей слева направо), ну и т.д.