Tugas

Mengingat traversal pre-order dan post-order dari pohon biner penuh, kembalikan traversal in-order.

Traversal akan direpresentasikan sebagai dua daftar, keduanya berisi n bilangan bulat positif yang berbeda, masing-masing secara unik mengidentifikasi sebuah node. Program Anda dapat mengambil daftar ini, dan menampilkan traversal in-order yang dihasilkan, menggunakan format I / O yang masuk akal.

Anda dapat menganggap input tersebut valid (yaitu, daftar sebenarnya mewakili traversal dari beberapa pohon).

Ini adalah kode-golf , jadi kode terpendek dalam byte menang.

Definisi

Sebuah pohon biner penuh adalah struktur terbatas node , diwakili di sini oleh bilangan bulat positif yang unik.

Pohon biner penuh adalah daun , terdiri dari satu simpul :

                                      1

Atau cabang , yang terdiri dari satu simpul dengan dua sub pohon (disebut sub pohon kiri dan kanan ), yang masing-masing, pada gilirannya, pohon biner penuh:

                                      1
                                    /   \
                                  …       …

Berikut adalah contoh lengkap dari pohon biner penuh:

                                        6
                                      /   \
                                    3       4
                                   / \     / \
                                  1   8   5   7
                                     / \
                                    2   9

The pre-order traversal dari pohon biner penuh rekursif didefinisikan sebagai berikut:

• Traversal pre-order dari daun yang mengandung simpul n adalah daftar [ n ].
• Traversal pre-order dari cabang yang berisi simpul n dan sub-pohon (L, R) adalah daftar [ n ] +  preorder ( L ) +  preorder ( R ), di mana + adalah operator gabungan daftar.

Untuk pohon di atas, itu [6, 3, 1, 8, 2, 9, 4, 5, 7] .

Travers post-order dari pohon biner penuh didefinisikan secara rekursif sebagai berikut:

• Traversal post-order dari daun yang mengandung simpul n adalah daftar [ n ].
• Travers post-order dari cabang yang berisi simpul n dan sub-pohon (L, R) adalah daftar postorder ( L ) +  postorder ( R ) + [ n ].

Untuk pohon di atas, bahwa ini [1, 2, 9, 8, 3, 5, 7, 4, 6] .

The in-order traversal dari pohon biner penuh rekursif didefinisikan sebagai berikut:

• Traversal berurutan dari daun yang mengandung simpul n adalah daftar [ n ].
• Travers berurutan cabang yang berisi simpul n dan sub-pohon (L, R) adalah daftar inorder ( L ) + [ n ] +  inorder ( R ).

Untuk pohon di atas, itu [1, 3, 2, 8, 9, 6, 5, 4, 7] .

Kesimpulannya: diberi pasangan daftar [6, 3, 1, 8, 2, 9, 4, 5, 7] (pra) dan [1, 2, 9, 8, 3, 5, 7, 4, 6] (pos) sebagai input, program Anda harus menampilkan [1, 3, 2, 8, 9, 6, 5, 4, 7] .

Uji kasus

Setiap test case dalam format 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]

Perl, 69 66 62 56 53 byte

Termasuk +1 untuk -p

Mengambil postorder diikuti oleh preorder sebagai satu baris yang dipisahkan oleh spasi di STDIN (perhatikan urutan pre dan post). Node direpresentasikan sebagai huruf unik (karakter apa pun yang bukan spasi atau baris baru OK).

inpost.pl <<< "98231 12983"

inpost.pl:

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

Menggunakan format numerik murni yang asli membutuhkan lebih banyak perhatian untuk mengidentifikasi satu angka dan muncul pada 73 byte

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

Digunakan sebagai

inpostnum.pl <<< "11,12,10,2,8,4,5,3,7 7,8,10,11,12,2,3,4,5"

Haskell, 84 83 byte

(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

JavaScript (ES6), 100 byte

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]

I / O terdiri dari karakter "aman" (mis. Huruf atau angka). Pendekatan alternatif, juga 100 byte:

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]