задача
Если заданы обратные и полные обходы полного двоичного дерева, верните его обратный порядок.
Обходы будут представлены в виде двух списков , каждый из которых содержит n различных положительных целых чисел, каждый из которых однозначно идентифицирует узел. Ваша программа может взять эти списки и вывести итоговый обход в порядке, используя любой разумный формат ввода / вывода.
Вы можете предположить, что ввод действителен (то есть списки фактически представляют обходы некоторого дерева).
Это код-гольф , поэтому выигрывает самый короткий код в байтах.
Определения
Полное бинарное дерево является конечной структурой узлов , представленной здесь уникальными положительными целыми числами.
Полное двоичное дерево - это либо лист , состоящий из одного узла :
1
Или ветвь , состоящая из одного узла с двумя поддеревьями (называемыми левым и правым поддеревьями ), каждое из которых, в свою очередь, представляет собой полное двоичное дерево:
1 / \ … …
Вот полный пример полного двоичного дерева:
6
/ \
3 4
/ \ / \
1 8 5 7
/ \
2 9
Обход предзаказа полного двоичного дерева рекурсивно определяется следующим образом:
- Предварительный заказ обход из листа , содержащего узел п список [ п ].
- Предварительный порядок обхода ветви, содержащей узел n и поддеревья (L, R), представляет собой список [ n ] + preorder ( L ) + preorder ( R ), где + - оператор объединения списков.
Для приведенного выше дерева это [6, 3, 1, 8, 2, 9, 4, 5, 7] .
Последовательный обход полного двоичного дерева рекурсивно определяется следующим образом:
- Последовательный обход листа, содержащего узел n, представляет собой список [ n ].
- Последовательный обход ветви, содержащей узел n и поддеревья (L, R), представляет собой список порядка ( L ) + порядок ( R ) + [ n ].
Для приведенного выше дерева это [1, 2, 9, 8, 3, 5, 7, 4, 6] .
Обход в заказе полного двоичного дерева рекурсивно определяются следующим образом :
- Порядок обхода листа, содержащего узел n, представляет собой список [ n ].
- Порядок обхода ветви, содержащей узел n и поддеревья (L, R), представляет собой список порядка ( L ) + [ n ] + порядок ( R ).
Для приведенного выше дерева это [1, 3, 2, 8, 9, 6, 5, 4, 7] .
В заключение: приведена пара списков [6, 3, 1, 8, 2, 9, 4, 5, 7] (предварительно) и [1, 2, 9, 8, 3, 5, 7, 4, 6] (post) в качестве входных данных ваша программа должна выводить [1, 3, 2, 8, 9, 6, 5, 4, 7] .
Контрольные примеры
Каждый тестовый пример имеет свой формат preorder, postorder → expected output
.
[8], [8] → [8]
[3,4,5], [4,5,3] → [4,3,5]
[1,2,9,8,3], [9,8,2,3,1] → [9,2,8,1,3]
[7,8,10,11,12,2,3,4,5], [11,12,10,2,8,4,5,3,7] → [11,10,12,8,2,7,4,3,5]
[1,2,3,4,5,6,7,8,9], [5,6,4,7,3,8,2,9,1] → [5,4,6,3,7,2,8,1,9]
"CDE" and "DEC" give "DCE"
? (даже используя юникодные буквы, если мне нужно много узлов)"CDE"
оно не сильно отличается от[67, 68, 69]
:)Ответы:
Perl,
6966625653 байтаВключает +1 для
-p
Принимает postorder с последующим preorder как одну строку, разделенную пробелом на STDIN (обратите внимание на порядок pre и post). Узлы представлены как уникальные буквы (любой символ, который не является пробелом или переводом строки, в порядке).
inpost.pl
:Использование оригинального чисто числового формата требует гораздо большей осторожности для точной идентификации одного числа и занимает 73 байта.
Использовать как
источник
-p
добавляет;
в конце, так что вам не нужно последнее;
.s;.* ;;
->s;.* ;
;
в конце. Но -p на самом деле добавляет\n;
в программу конец-e
. В файл он добавляется только;
тогда и только тогда, когда файл не заканчивается\n
. Поскольку я хочу претендовать-p
как +1, а не +3, программа должна работать из командной строки, поэтому с-e
. И я не хочу ложного перевода строки в выводе, который я тогда получу'
? Если вы запускаете его так, как он есть (вызываете файл<<<
), вы можете оставить последнее;
отключенным.'
или используетdo$0
и т. Д.), Я всегда получаю оценку-p
+3 (пробел, минус, p), но если код также будет работать в командной строке, где вы получаете-e
и'
бесплатно я оцениваю его, так+1
как он может быть связан сe
'
бесплатно. Спасибо за разъяснение.Haskell,
8483 байтаисточник
JavaScript (ES6), 100 байт
Ввод / вывод выполняется в виде строк «безопасных» символов (например, букв или цифр). Альтернативный подход, также 100 байтов:
источник