Предварительный заказ + постзаказ на заказ

11

задача

Если заданы обратные и полные обходы полного двоичного дерева, верните его обратный порядок.

Обходы будут представлены в виде двух списков , каждый из которых содержит 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]
Линн
источник
Поскольку входные данные гарантированно имеют определенную форму (полное двоичное дерево), вам не нужны оба входа, не так ли?
feersum
Двоичное дерево заполнено , но не завершено , поэтому дерево с n- элементами может иметь много форм, и, в общем, вам нужны оба.
Линн
Могу ли я представить узлы в виде отдельных букв, дающих строки для заказов. Например , второй пример стал бы: "CDE" and "DEC" give "DCE"? (даже используя юникодные буквы, если мне нужно много узлов)
Тон Хоспел
@TonHospel Я бы с этим согласился - возможно, все, что вы делаете, это немного расширяете определение списка целых чисел , потому что "CDE"оно не сильно отличается от [67, 68, 69]:)
Линн

Ответы:

2

Perl, 69 66 62 56 53 байта

Включает +1 для -p

Принимает postorder с последующим preorder как одну строку, разделенную пробелом на STDIN (обратите внимание на порядок pre и post). Узлы представлены как уникальные буквы (любой символ, который не является пробелом или переводом строки, в порядке).

inpost.pl <<< "98231 12983"

inpost.pl:

#!/usr/bin/perl -p
s%(.)(.)+\K(.)(.+)\3(\1.*)\2%$4$5$3$2%&&redo;s;.+ ;;

Использование оригинального чисто числового формата требует гораздо большей осторожности для точной идентификации одного числа и занимает 73 байта.

#!/usr/bin/perl -p
s%\b(\d+)(,\d+)+\K,(\d+\b)(.+)\b\3,(\1\b.*)\2\b%$4$5,$3$2%&&redo;s;.+ ;;

Использовать как

inpostnum.pl <<< "11,12,10,2,8,4,5,3,7 7,8,10,11,12,2,3,4,5"
Тон Хоспел
источник
-pдобавляет ;в конце, так что вам не нужно последнее ;. s;.* ;;->s;.* ;
Райли
@ Райли, я знаю. Вот почему у меня есть ;в конце. Но -p на самом деле добавляет \n;в программу конец -e. В файл он добавляется только ;тогда и только тогда, когда файл не заканчивается \n. Поскольку я хочу претендовать -pкак +1, а не +3, программа должна работать из командной строки, поэтому с -e. И я не хочу ложного перевода строки в выводе, который я тогда получу
Тон Хоспел
Если вы запускаете его в командной строке, разве вам это не нужно '? Если вы запускаете его так, как он есть (вызываете файл <<<), вы можете оставить последнее ;отключенным.
Райли
@Riley Это зависит от интерпретации метода оценки для perl. Я обычно представляю свой код в виде файла, так как считаю, что он менее эфемерный. Но если вы посмотрите на мои материалы, вы увидите, что если код должен быть в файле (потому что, например, он имеет 'или использует do$0и т. Д.), Я всегда получаю оценку -p+3 (пробел, минус, p), но если код также будет работать в командной строке, где вы получаете -eи 'бесплатно я оцениваю его, так +1как он может быть связан сe
Тон Хоспел
Ладно, я просто не понял, как именно оцениваются представления в командной строке. Я не осознавал, что ты получаешь 'бесплатно. Спасибо за разъяснение.
Райли
3

Haskell, 84 83 байта

(a:b:c)#z|i<-1+length(fst$span(/=b)z),h<- \f->f i(b:c)#f i z=h take++a:h drop
a#_=a
Дайан
источник
2

JavaScript (ES6), 100 байт

f=(s,t,l=t.search(s[1]))=>s[1]?f(s.slice(1,++l+1),t.slice(0,l))+s[0]+f(s.slice(l+1),t.slice(l)):s[0]

Ввод / вывод выполняется в виде строк «безопасных» символов (например, букв или цифр). Альтернативный подход, также 100 байтов:

f=(s,t,a=0,b=0,c=s.length-1,l=t.search(s[a+1])-b)=>c?f(s,t,a+1,b,l)+s[a]+f(s,t,l+2+a,l+1,c-l-2):s[a]
Нил
источник