Balanced Binary Tree

+10

array root menyimpan pohon biner. Akar berada di indeks 0, anak-anak dari indeks i berada di 2*i+1 (kiri) dan 2*i+2 (kanan), -1 menandai posisi kosong, dan entri -1 tambahan dapat berada di akhir.

Kembalikan true jika pohon tersebut seimbang berdasarkan tinggi, artinya pada setiap simpul, tinggi subtree kiri dan kanan berbeda paling banyak 1, dan false jika tidak. Tinggi subtree adalah jumlah simpul pada jalur menurun terpanjangnya. Subtree kosong memiliki tinggi 0.

Fungsi

isBalanced(root: integer-array) → boolean

rootinteger-array: pohon biner dalam urutan level, dengan -1 untuk posisi kosong
Mengembalikanboolean: true jika tinggi kedua subpohon setiap node berbeda paling banyak 1, false jika tidak

Batasan

1 ≤ root.length ≤ 32767
Setiap root[i] bernilai -1 atau nilai dengan 0 ≤ root[i] ≤ 10⁵.
root[0] tidak pernah -1, jadi pohon memiliki setidaknya satu simpul.
array tersebut mungkin diakhiri dengan entri -1 tambahan setelah node terakhir.
Kedua anak dari posisi kosong juga kosong, dan kedalamannya paling banyak 14.
Nilai node berbeda-beda.

Contoh

Input: root = [5, 2, 9, -1, -1, 7, 11]
Output: true
Penjelasan: Subpohon kiri dari akar adalah satu-satunya node 2, dengan tinggi 1. Subpohon kanannya, yang terdiri dari 9, 7, dan 11, memiliki tinggi 2. Selisihnya adalah 1, dan setiap node lainnya memiliki dua subpohon dengan tinggi yang sama.

Input: root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
Output: false
Penjelasan: Kedua sisi root memiliki tinggi 3, tetapi node 3 gagal: subtree kirinya 1, 0 memiliki tinggi 2 dan subtree kanannya kosong.

Input: root = [4, 2, -1, 1]
Output: false
Penjelasan: Root memiliki rantai 2, 1 di sebelah kiri dengan tinggi 2, dan tidak ada apa pun di sebelah kanan dengan tinggi 0. Selisih sebesar 2 terlalu besar.

Pertanyaan lanjutan

Bisakah kamu memeriksa pohon tanpa rekursi, menggunakan stack eksplisit?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Aturan ini berlaku di setiap node, jadi pohon yang akarnya tampak genap tetap bisa gagal di bagian bawah, seperti yang terjadi pada contoh kedua di 3. Penelusuran post-order menghitung tinggi setiap subtree satu kali dan meneruskan kegagalan ke atas segera setelah kegagalan muncul, dalam O(n).

Hitung ulang tinggi di setiap node

Intuisi

Ubah definisi menjadi kode. height(i) bernilai 0 pada posisi kosong dan bernilai 1 lebih besar dari tinggi anak yang lebih tinggi di tempat lain. Bandingkan tinggi kedua anak di setiap node yang ada. Node pertama yang tinggi kedua anaknya berbeda lebih dari 1 membuat jawabannya false.

Setiap pemeriksaan menelusuri seluruh subtree di bawah node-nya, jadi setiap node ditelusuri sekali untuk setiap node di atasnya: O(n·h). Dengan paling banyak 14 level, tree penuh yang terdiri dari 16,383 node membutuhkan sekitar 2 × 10^5 langkah. Rantai yang terdiri dari n node membutuhkan O(n²).

Algoritma

Tentukan height(i) sebagai 0 untuk indeks yang melewati akhir atau bernilai -1, dan sebagai 1 + max(height(2*i+1), height(2*i+2)) untuk node yang valid.
Kunjungi setiap indeks i yang berisi node yang valid.
Jika height(2*i+1) dan height(2*i+2) berbeda lebih dari 1, kembalikan false.
Jika perulangan berakhir tanpa kegagalan, kembalikan true.

def isBalanced(root):
    n = len(root)

    def height(i):
        # The number of nodes on the longest downward path from index i.
        if i >= n or root[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    # Check every real node, measuring both subtrees from scratch.
    for i in range(n):
        if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
            return False
    return True

Satu penelusuran post-order yang melaporkan tinggi atau kegagalan

Intuisi

Pemeriksaan pada sebuah node memerlukan tinggi kedua subtree-nya, dan tinggi itulah yang juga perlu dilaporkan node untuk menunjukkan tingginya sendiri. Jadi, dapatkan keduanya dalam satu kunjungan post-order: setiap pemanggilan mengembalikan tinggi subtree-nya setelah kedua anaknya selesai diproses.

Kegagalan di bagian bawah juga harus diteruskan ke atas. Tinggi yang sebenarnya tidak pernah negatif, jadi gunakan -1 untuk menandainya: sebuah pemanggilan mengembalikan -1 ketika salah satu anak mengembalikan -1 atau tinggi kedua anak berbeda lebih dari 1. Dalam contoh kedua, 3 melihat tinggi 2 dan 0, lalu mengembalikan -1, dan root meneruskannya tanpa mengunjungi sisi kanannya.

Tidak ada node yang dikunjungi dua kali, jadi waktunya O(n), dengan O(h) pemanggilan di stack.

Algoritma

Tulis check(i). Untuk indeks yang melewati akhir atau -1, kembalikan 0.
Hitung left = check(2*i+1). Jika nilainya -1, kembalikan -1.
Hitung right = check(2*i+2). Jika nilainya -1, atau selisih left dan right lebih dari 1, kembalikan -1.
Jika tidak, kembalikan 1 + max(left, right).
Kembalikan apakah check(0) bukan -1.

def isBalanced(root):
    n = len(root)

    def check(i):
        # The height of the subtree at index i, or -1 if it is not balanced.
        if i >= n or root[i] == -1:
            return 0
        left = check(2 * i + 1)
        if left == -1:
            return -1
        right = check(2 * i + 2)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(0) != -1

Jebakan dan kasus tepi

Hanya memeriksa akar. Pada contoh kedua, kedua sisi akar memiliki tinggi 3, tetapi simpul 3 memiliki selisih 2.
Membandingkan daun yang paling dangkal dan paling dalam. Pohon seimbang terkecil dengan tinggi 6 memiliki daun pada kedalaman 4 dan 6, dan setiap simpul di dalamnya lolos.
Kehilangan informasi kegagalan saat naik. Jika simpul anak mengembalikan -1 dan simpul induk menghitung 1 + max(-1, 2), kegagalan berubah kembali menjadi tinggi.
Menggunakan panjang array sebagai tinggi. Entri -1 di bagian akhir membuat array lebih panjang daripada kedalaman pohon.
Di Lua dan R, indeks array dimulai dari 1. Pertahankan indeks simpul berbasis 0 untuk 2*i+1 dan baca root[i + 1].

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Balanced Binary Tree?

Satu penelusuran post-order mengunjungi setiap node satu kali: waktu O(n) dan ruang stack O(h) untuk tree dengan tinggi h. Menghitung ulang tinggi di setiap node membutuhkan biaya O(n·h), yang menjadi O(n²) pada rantai.

Apa arti seimbang tinggi untuk pohon biner?

Pada setiap node, tinggi subtree kiri dan kanan berbeda paling banyak 1. AVL tree memulihkan sifat ini setelah setiap penyisipan dan penghapusan, sehingga tingginya tetap O(log n).

Apakah pohon biner lengkap selalu seimbang?

Ya. Setiap level pada pohon lengkap terisi penuh, kecuali mungkin level terakhir, yang terisi dari kiri, sehingga tinggi kedua subpohon pada simpul mana pun berbeda paling banyak 1. Kebalikannya tidak benar: pohon seimbang bisa memiliki celah di sisi kiri level terakhirnya.

def isBalanced(root):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

root = [5, 2, 9, -1, -1, 7, 11]

Output yang diharapkan

true