Diameter of Binary Tree

Q: Berapa kompleksitas waktu Diameter of Binary Tree?

Solusi post-order mengunjungi setiap node satu kali: waktu O(n) dan ruang tambahan O(h) untuk rekursi, dengan h sebagai tinggi pohon. Menghitung tinggi secara terpisah di setiap node membutuhkan biaya O(n·h) , yaitu O(n²) pada pohon berbentuk rantai.

MudahTree traversal

+10

Kamu mendapatkan pohon biner yang disimpan dalam array tree dengan urutan level. Akar berada di indeks 0, anak dari simpul di indeks i berada di 2*i+1 (kiri) dan 2*i+2 (kanan), -1 menandai tempat kosong, dan array dapat diakhiri dengan entri -1 tambahan. Kembalikan diameter pohon: jumlah sisi pada jalur terpanjang antara dua simpul mana pun. Jalur tersebut dapat melewati akar atau tetap berada di dalam satu subtree.

Fungsi

diameterOfBinaryTree(tree: integer-array) → integer

treeinteger-array: pohon biner dalam urutan level, dengan -1 untuk posisi kosong
Mengembalikaninteger: jumlah sisi pada jalur terpanjang antara dua node

Batasan

1 ≤ tree.length ≤ 32767
Setiap tree[i] bernilai -1 atau nilai dengan 0 ≤ tree[i] ≤ 1000.
tree[0] tidak pernah -1, jadi tree memiliki setidaknya satu node.
array dapat diakhiri dengan entri -1 tambahan setelah node terakhir.
Kedua child dari posisi kosong juga kosong, dan kedalamannya paling banyak 14.

Contoh

Input: tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
Output: 4
Penjelasan: Jalur 7, 4, 3, 8, 6 memiliki lima simpul dan empat sisi. Jalur ini berbelok di akar: tiga sisi ke bawah di kiri, satu ke bawah di kanan.

Input: tree = [2, 5, -1, 1, 9, -1, -1, 3, -1, -1, 4]
Output: 4
Penjelasan: Jalur 3, 1, 5, 9, 4 memiliki empat sisi dan berbelok di 5 pada indeks 1. Root tidak memiliki anak kanan, jadi jalur yang melewatinya hanya memiliki tiga sisi.

Input: tree = [6, -1, -1]
Output: 0
Penjelasan: Satu node tidak memiliki edge. Jalur terpanjang adalah node itu sendiri, dengan panjang 0.

Pertanyaan lanjutan

Bagaimana cara mengembalikan jalurnya sendiri, yaitu nilai node dari satu ujung diameter ke ujung lainnya?

Petunjuk

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

0 dari 3 dibuka

Solusi

Jalur terpanjang tidak harus melewati akar. Setiap jalur memiliki satu simpul tertinggi, tempat jalur itu berbelok, dan jalur terpanjang yang berbelok di sebuah simpul memiliki tinggi kiri ditambah tinggi kanan dalam satuan sisi. Satu lintasan post-order menghitung setiap tinggi dari bawah ke atas dan memeriksa setiap titik belok, dalam O(n).

Ukur setiap pasangan simpul

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Ukur setiap pasangan node. Parent dari indeks i adalah (i-1)/2, dibulatkan ke bawah, jadi jarak antara indeks a dan b adalah berapa kali kamu mengganti indeks yang lebih besar dengan parent-nya sebelum keduanya bertemu. Indeks yang lebih besar tidak pernah berada pada level yang lebih tinggi, jadi indeks itu tidak akan melewati titik pertemuan. Untuk 9 dan 2 pada contoh pertama: 9 ke 4 ke 1, 2 ke 0, 1 ke 0, empat langkah.

Pohon penuh dengan 16383 node memiliki sekitar 1.3 × 10^8 pasangan, masing-masing hingga 26 langkah: miliaran langkah untuk satu jawaban.

Algoritma

Kumpulkan indeks semua node nyata.
Untuk setiap pasangan (a, b), tetapkan edges = 0 dan ulangi sampai a == b: ganti indeks yang lebih besar dengan parent-nya dan tambahkan 1 ke edges.
Simpan nilai edges terbesar yang kamu temukan, lalu kembalikan nilai tersebut.

def diameterOfBinaryTree(tree):
    nodes = [i for i, value in enumerate(tree) if value != -1]
    best = 0
    for x in range(len(nodes)):
        for y in range(x + 1, len(nodes)):
            a, b = nodes[x], nodes[y]
            edges = 0
            while a != b:
                # A larger index is never higher up, so climb from it.
                if a > b:
                    a = (a - 1) // 2
                else:
                    b = (b - 1) // 2
                edges += 1
            best = max(best, edges)
    return best

Ukur kedua tinggi di setiap node

Intuisi

Biarkan height(c) menghitung jumlah node pada jalur menurun terpanjang dari c, dengan nilai 0 untuk posisi kosong. Jalur terpanjang yang berbelok di node i memiliki height(2*i+1) + height(2*i+2) edge, satu untuk setiap node di bawah titik belok. Coba setiap node sebagai titik belok dan simpan hasil terbaik. Pada contoh kedua, 5 di indeks 1 memiliki tinggi 2 di setiap sisi, total empat edge, sedangkan root hanya menghasilkan 3 + 0.

Setiap pemanggilan height menelusuri seluruh subtree, dan sebuah node ditelusuri lagi untuk setiap ancestor, sehingga kompleksitasnya O(n·h). Dengan h ≤ 14, cara ini cepat, tetapi pada pohon berbentuk rantai kompleksitasnya menjadi O(n²).

Algoritma

Tulis height(i): 0 untuk tempat kosong, jika tidak, 1 + max(height(2*i+1), height(2*i+2)).
Untuk setiap simpul yang ada i, hitung height(2*i+1) + height(2*i+2).
Kembalikan jumlah terbesar.

def diameterOfBinaryTree(tree):
    n = len(tree)

    def height(i):
        # Nodes on the longest downward path from i; an empty spot has 0.
        if i >= n or tree[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    best = 0
    for i in range(n):
        if tree[i] != -1:
            # The longest path that turns at node i goes down both sides.
            best = max(best, height(2 * i + 1) + height(2 * i + 2))
    return best

Satu penelusuran post-order pada tinggi

Intuisi

Tinggi sebuah node hanya membutuhkan tinggi anak-anaknya, yaitu dua angka yang sama dengan yang digunakan pemeriksaan titik balik. Traversal post-order menyelesaikan kedua anak sebelum induknya, sehingga di setiap node kamu memiliki left dan right: perbarui jawaban dengan left + right, lalu kembalikan 1 + max(left, right) ke induknya.

Dalam contoh pertama, 7 mengembalikan 1, 4 mengembalikan 2, dan 3 mengembalikan 3. 6 mengembalikan 1, jadi di root left + right = 3 + 1 = 4. Setiap node dikunjungi satu kali: waktu O(n), dan kedalaman rekursinya adalah O(h).

Algoritma

Tetapkan best = 0 dan tulis height(i). Untuk tempat kosong, kembalikan 0.
Hitung left = height(2*i+1) dan right = height(2*i+2).
Tetapkan best ke nilai yang lebih besar antara best dan left + right.
Kembalikan 1 + max(left, right).
Panggil height(0) dan kembalikan best.

def diameterOfBinaryTree(tree):
    n = len(tree)
    best = 0

    def height(i):
        # Returns the height of node i and updates best on the way back up.
        nonlocal best
        if i >= n or tree[i] == -1:
            return 0
        left = height(2 * i + 1)
        right = height(2 * i + 2)
        best = max(best, left + right)  # the longest path that turns at node i
        return 1 + max(left, right)

    height(0)
    return best

Jebakan dan kasus tepi

Menghitung node, bukan edge. Jalur 7, 4, 3, 8, 6 memiliki lima node, tetapi panjangnya 4.
Mengukur hanya melalui root. Pada contoh kedua, hasilnya tiga, padahal jawabannya empat.
Mengembalikan diameter dari pemanggilan rekursif. Parent membutuhkan tinggi, jadi simpan diameter dalam variabel terpisah.
Mencampur konvensi tinggi. Tinggi yang menghitung node, dengan 0 untuk posisi kosong, menghasilkan left + right edge. Tinggi yang menghitung edge membutuhkan -1 untuk posisi kosong dan left + right + 2. Mencampur keduanya membuat hasil meleset satu atau dua.
Membaca melewati akhir. Leaf yang dekat dengan akhir array memiliki indeks child yang melewati entri terakhirnya. Perlakukan indeks tersebut sebagai posisi kosong.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Diameter of Binary Tree?

Solusi post-order mengunjungi setiap node satu kali: waktu O(n) dan ruang tambahan O(h) untuk rekursi, dengan h sebagai tinggi pohon. Menghitung tinggi secara terpisah di setiap node membutuhkan biaya O(n·h), yaitu O(n²) pada pohon berbentuk rantai.

Apakah diameter pohon biner selalu melewati root?

Tidak. Jalur terpanjang bisa berada di dalam satu subtree, misalnya saat root memiliki satu cabang pendek dan subtree yang dalam serta rimbun di sisi lainnya. Itulah sebabnya kamu memeriksa left + right di setiap node.

Bagaimana cara mencari diameter pohon biner tanpa rekursi?

Kunjungi node sehingga setiap child muncul sebelum parent-nya: masukkan root ke stack, keluarkan node ke dalam list sambil memasukkan child-nya, lalu telusuri list itu dari belakang. Simpan setiap tinggi dalam array dan perbarui jawaban menggunakan tinggi kedua child di setiap node. Waktunya tetap O(n).

def diameterOfBinaryTree(tree):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]

Output yang diharapkan

Diameter of Binary Tree

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Ukur setiap pasangan simpul

Ukur kedua tinggi di setiap node

Satu penelusuran post-order pada tinggi

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa