Ketinggian pohon biner adalah jarak dari simpul akar ke simpul anak yang paling jauh dari akar.
Di bawah ini adalah contohnya:
2 <-- root: Height 1
/ \
7 5 <-- Height 2
/ \ \
2 6 9 <-- Height 3
/ \ /
5 11 4 <-- Height 4
Tinggi pohon biner: 4
Definisi Pohon Biner
Pohon adalah objek yang berisi nilai integer yang ditandatangani dan dua pohon lain atau pointer ke sana.
Struktur struct pohon biner terlihat seperti berikut:
typedef struct tree
{
struct tree * l;
struct tree * r;
int v;
} tree;
Tantangan:
Memasukkan
Akar pohon biner
Keluaran
Angka yang mewakili ketinggian pohon biner
Dengan asumsi Anda diberi root dari pohon biner sebagai input, tulis program terpendek yang menghitung ketinggian pohon biner dan kembalikan tingginya. Program dengan jumlah byte terkecil (spasi akuntansi) menang.
code-golf
binary-tree
T. Salim
sumber
sumber
h
. Mungkin lebih baik untuk mendefinisikan struktur spesifik yang dibuat hanya dari daftar untuk tujuan tantangan ini.[root_value, left_node, right_node]
mana masing-masingleft_node
danright_node
juga pohon biner dapat diterima? Itu akan sepele dalam banyak bahasa, tetapi mungkin menyenangkan dalam beberapa bahasa lain.a tree is an object that contains a value and either two other trees or pointers to them
. Definisi yang termasuk bahasa tanpa objek juga akan bagus.Jawaban:
Jelly , 3 byte
Tautan monadik yang menerima daftar yang mewakili pohon:, di
[root_value, left_tree, right_tree]
mana masing-masingleft_tree
danright_tree
merupakan struktur yang sama (kosong jika perlu), yang menghasilkan ketinggian.Cobalah online!
Bagaimana?
Sepele di Jelly:
sumber
x
ganti[x, [], []]
...Python 2 ,
3533 byteTerima kasih kepada Arnauld karena telah melihat pengawasan dan penghematan 4.
Fungsi rekursif menerima daftar yang mewakili pohon:, di
[root_value, left_tree, right_tree]
mana masing-masingleft_tree
danright_tree
struktur yang sama (kosong jika perlu), yang mengembalikan ketinggian.Cobalah online!
Perhatikan bahwa
[]
akan kembaliFalse
, tetapi dengan PythonFalse==0
.sumber
Haskell, 33 byte
Menggunakan jenis pohon kustom
data T = L | N T T Int
, yang setara dengan Haskell dari struct C yang diberikan dalam tantangan.Cobalah online!
sumber
Perl 6 , 25 byte
Input adalah daftar 3-elemen
(l, r, v)
. Pohon kosong adalah daftar kosong.Cobalah online!
Penjelasan
Solusi lama, 30 byte
Cobalah online!
sumber
&?BLOCK
trick menarik tapi itu beberapa byte lebih pendek untuk menetapkan blok untuk $!$!
atau$/
terasa seperti curang bagi saya.05AB1E ,
1175 byte-4 byte terima kasih kepada @ExpiredData .
-2 byte terima kasih kepada @Grimy .
Format input mirip dengan jawaban Jelly: daftar yang merepresentasikan pohon:, di
[root_value, left_tree, right_tree]
mana masing-masingleft_tree
danright_tree
merupakan struktur yang serupa (opsional kosong). Yaitu[2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]
mewakili pohon dari deskripsi tantangan.Cobalah secara online atau verifikasi beberapa kasus uji lagi .
Penjelasan:
Perhatikan bahwa meskipun 05AB1E berbasis 0, loop perubahan
Δ
menyebabkan indeks output menjadi benar, karena memerlukan iterasi tambahan untuk memeriksa tidak ada perubahan lagi.sumber
JavaScript (ES6),
3533 byteStruktur input:
[[left_node], [right_node], value]
Cobalah online!
Berkomentar
sumber
a&&-~
.C, 43 byte
Struktur pohon biner adalah sebagai berikut:
sumber
JavaScript (Node.js) , 32 byte
Cobalah online!
Menggunakan namaflat
sebagai gantiflatten
atausmoosh
merupakan ide bagus untuk kode golf.Menggunakan
[]
untuk simpul nol di pohon, dan[left, right, value]
untuk simpul.value
di sini adalah bilangan bulat.sumber
Bahasa Wolfram (Mathematica) , 10 byte
Cobalah online! Mengambil input sebagai daftar bersarang
{v, l, r}
.sumber
2[7[2,6[5,11]],5[9[4,],]]
merupakan representasi yang valid dari pohon,Depth
bekerjaHaskell, 28 byte
Menggunakan definisi data berikut:
Tingginya adalah:
sumber
Skema, 72 Bytes
Versi Lebih Mudah Dibaca:
Menggunakan daftar formulir (data, kiri, kanan) untuk mewakili pohon. Misalnya
Cobalah secara Online!
sumber
R , 51 byte
Cobalah online!
Input: daftar bersarang dalam format:
list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)
Algoritma: Iteratif meratakan pohon dengan satu tingkat sampai menjadi vektor datar: jumlah iterasi sesuai dengan kedalaman maks.
Terinspirasi oleh solusi @KevinCruijssen
Alternatif rekursif:
R , 64 byte
Cobalah online!
Mendefinisikan ulang fungsi / operator
'~'
sehingga dapat menghitung kedalaman maksimum pohon yang disimpan dalam struktur daftar.Struktur daftar pohon dalam format:
list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)
sumber
d=1
dan kemudiand-1
pada akhirnya? Tidak bisakah Anda memulai0
?>
ke~
sini sehingga kasus uji lebih mudah untuk dimasukkanJapt , 8 byte
Cobalah
Asli, 9 byte
Cobalah
sumber
K (ngn / k) , 4 byte
Larutan:
Cobalah online!
Penjelasan:
Saya pikir saya mungkin telah melewatkan intinya.
Merepresentasikan pohon sebagai daftar 3-item (parent-node; left-child; right-child), contohnya dapat direpresentasikan sebagai
atau:
(2;(7;(,2);(6;(,5);(,11)));(5;();(9;(,4);())))
.Jadi solusinya adalah dengan meratakan iteratif, dan hitung iterasinya:
sumber
Arang , 29 byte
Cobalah online! Tautan adalah untuk mengucapkan versi kode. Memodifikasi sementara pohon selama pemrosesan. Penjelasan:
Tekan nol ke simpul akar.
Dorong simpul root ke daftar semua node.
Lakukan pencarian pertama dari pohon.
Dapatkan kedalaman node ini.
Ulangi simpul anak.
Beri tahu simpul anak kedalaman orangtuanya dan dorong ke daftar semua simpul.
Setelah semua node telah dilintasi, cetak kedalaman node terakhir. Karena traversal pertama kali lebarnya, ini akan menjadi ketinggian pohon.
sumber
Stax , 5 byte
Jalankan dan debug itu
Stax tidak memiliki pointer atau nilai null, jadi saya mewakili input seperti
[2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]
. Mungkin itu keuntungan yang tidak adil, tapi itulah yang paling dekat yang bisa saya dapatkan.Dibongkar, tidak diseret, dan dikomentari, kode ini terlihat seperti ini.
Jalankan yang ini
sumber
Kotlin, 45 byte
Dengan asumsi kelas berikut didefinisikan
Cobalah online
sumber
Julia, 27 byte
Dengan struct berikut mewakili pohon biner:
c
adalah tuple yang mewakili node kiri dan kanan dan tuple kosong()
digunakan untuk memberi sinyal tidak adanya node.sumber
Kotlin , 42 byte
Cobalah online!
Dimana
sumber