Bottom View of Binary Tree

Q: Berapa kompleksitas waktu untuk tampilan bawah pohon biner?

O(n) untuk n node: breadth-first search menangani setiap node satu kali dengan satu penulisan hash map. Map terurut seperti tree map menambahkan faktor log w untuk w kolom.

SedangTree traversal Hashing

+10

array root menyimpan pohon biner: root berada di indeks 0, anak-anak dari indeks i berada di 2i+1 (kiri) dan 2i+2 (kanan), -1 menandakan tempat kosong, dan mungkin ada entri -1 tambahan di akhir.

Root berada di kolom 0; langkah ke kiri berpindah satu kolom ke kiri, langkah ke kanan berpindah satu kolom ke kanan. Jika dilihat dari bawah, setiap kolom menampilkan node terdalamnya, dan jika kedalamannya sama, node terakhir pada tingkat tersebut saat dibaca dari kiri ke kanan (indeks yang lebih besar). Kembalikan nilai yang terlihat, mulai dari kolom paling kiri.

Fungsi

bottomView(root: integer-array) → integer-array

rootinteger-array: pohon dalam urutan heap, dengan -1 untuk posisi kosong
Mengembalikaninteger-array: nilai yang terlihat dari bawah di setiap kolom, dimulai dari kolom paling kiri

Batasan

1 ≤ root.length ≤ 32767
Setiap root[i] adalah -1 atau nilai dengan 0 ≤ root[i] ≤ 10⁴, dan tidak ada nilai yang muncul dua kali.
root[0] tidak pernah -1, jadi pohon memiliki setidaknya satu simpul.
Entri tambahan -1 mungkin berada di akhir array, setelah node terakhir.
Kedua anak dari titik kosong juga kosong, dan pohon memiliki paling banyak 14 level.

Contoh

Input: root = [5, 2, 9, 4, 7, 1, 6]
Output: [4, 2, 1, 9, 6]
Penjelasan: Kolom 0 berisi 5 dan, dua tingkat di bawahnya, 7 (indeks 4) dan 1 (indeks 5). 1 muncul belakangan pada tingkat yang sama, jadi angka itu terlihat. Kolom -2, -1, 1, dan 2 berisi 4, 2, 9, dan 6.

Input: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Output: [5, 4, 3]
Penjelasan: Kolom -1 berisi 2 dan, dua tingkat di bawahnya, 5 (indeks 9), jadi kamu melihat 5. Di kolom 0, 4 berada di bawah akar. Kolom 1 hanya berisi 3.

Input: root = [8, -1, -1, -1]
Output: [8]
Penjelasan: Setiap posisi setelah akar adalah -1, jadi 8 adalah satu-satunya node dan kolom 0 adalah satu-satunya kolom.

Pertanyaan lanjutan

Jika nilai seri pada level terdalam suatu kolom harus mengembalikan setiap node yang seri, dari kiri ke kanan, bagaimana versi breadth-first akan berubah? Apa hasil kolom 0 dari contoh 1?

Solusi

Setiap kolom menampilkan node terdalamnya, dan jika seri, pilih node yang muncul belakangan dalam urutan level. Pencarian breadth-first mengunjungi node berdasarkan urutan level, jadi node terakhir yang dikunjunginya dalam suatu kolom adalah jawabannya: biarkan setiap node menimpa slot kolomnya.

Kedalaman pertama, node terdalam di setiap kolom

Intuisi

Telusuri pohon secara depth-first, berikan setiap node kolom dan kedalamannya, lalu simpan kedalaman dan nilai node terdalam sejauh ini untuk setiap kolom.

Mengunjungi subtree kiri sebelum subtree kanan membuat node-node pada satu level ditemui dari kiri ke kanan, jadi node yang kamu inginkan adalah node terakhir yang ditemui: ganti jika kedalamannya lebih besar atau sama. Pada contoh 1, penelusuran menemui 7 lalu 1, keduanya pada kedalaman 2 di kolom 0, dan 1 menjadi nilai kolom tersebut.

Kolom-kolom membentuk rentang yang tidak terputus, jadi catat kolom terkecil dan terbesar, lalu baca setiap kolom di antaranya. Mengunjungi setiap node satu kali membutuhkan waktu O(n), dan rekursi memiliki kedalaman h pemanggilan untuk pohon dengan h level.

Algoritma

Kunjungi root dengan kolom 0 dan kedalaman 0.
Lewati indeks i jika indeks tersebut berada di luar akhir array atau root[i] adalah -1.
Jika kolom belum memiliki node, atau kedalaman ini lebih besar dari atau sama dengan kedalaman yang tersimpan, simpan kedalaman dan nilainya.
Kunjungi 2i+1 dengan kolom col-1, lalu 2i+2 dengan kolom col+1, keduanya satu tingkat lebih dalam.
Kembalikan nilai-nilai yang tersimpan, dimulai dari kolom terkecil.

def bottomView(root):
    n = len(root)
    best = {}  # column -> (depth, value) of the deepest node found so far

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace on a greater or equal depth: on a tie, the node
        # met last is the one further right, which comes later in level order.
        if col not in best or depth >= best[col][0]:
            best[col] = (depth, root[i])
        visit(2 * i + 1, col - 1, depth + 1)
        visit(2 * i + 2, col + 1, depth + 1)

    visit(0, 0, 0)
    # The columns that hold a node form one unbroken range.
    return [best[col][1] for col in range(min(best), max(best) + 1)]

Penelusuran melebar lebih dahulu, simpul terakhir per kolom

Intuisi

Sebuah queue yang setiap kali node keluar akan menambahkan anak kirinya, lalu anak kanannya, mengeluarkan node berdasarkan urutan level: semua node dengan kedalaman d sebelum node mana pun dengan kedalaman d+1, dan setiap level dari kiri ke kanan. Di antara node-node dalam satu kolom, node terdalam keluar terakhir, dan jika kedalamannya sama, node yang lebih ke kanan keluar belakangan. Jadi, ketika setiap node menimpa slot kolomnya, setiap slot akhirnya menyimpan node yang terlihat dari bawah, tanpa perlu membandingkan kedalaman.

Dalam contoh 1, 7 menulis ke kolom 0 dan 1 menimpanya.

Setiap node membutuhkan satu kunjungan queue dan satu penulisan map: waktu O(n). Queue dapat menampung satu level penuh, sekitar setengah jumlah node, sehingga ruang yang dibutuhkan adalah O(n).

Algoritma

Masukkan pasangan (indeks 0, kolom 0) ke dalam antrean.
Ambil pasangan (i, col) dan simpan root[i] pada col, menggantikan nilai sebelumnya jika ada.
Tambahkan (2i+1, col-1), lalu (2i+2, col+1), untuk setiap anak yang berada di dalam array dan bukan -1.
Ulangi sampai antrean kosong, sambil melacak kolom terkecil dan terbesar.
Kembalikan nilai-nilai map, dimulai dari kolom terkecil.

from collections import deque


def bottomView(root):
    n = len(root)
    bottom = {}  # column -> value of the last node seen in that column
    queue = deque([(0, 0)])  # (node index, column); the root is never empty
    while queue:
        i, col = queue.popleft()
        # The queue hands out deeper nodes later, and right after left
        # on one level, so the last node to reach a column is the one seen from below.
        bottom[col] = root[i]
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and root[left] != -1:
            queue.append((left, col - 1))
        if right < n and root[right] != -1:
            queue.append((right, col + 1))
    # The columns that hold a node form one unbroken range.
    return [bottom[col] for col in range(min(bottom), max(bottom) + 1)]

Jebakan dan kasus tepi

Mengganti hanya saat kedalamannya benar-benar lebih besar pada versi depth-first. Contoh 1 kemudian mempertahankan 7, bukan 1.
Mempertahankan node pertama yang ditemukan oleh breadth-first search untuk setiap kolom. Itulah tampilan atas.
Menambahkan anak kanan ke antrean sebelum anak kiri. Setiap level kemudian muncul dari kanan ke kiri, dan jika kedalamannya sama, node yang dipilih keliru.
Mengambil daun sebagai jawaban. Pada contoh 1, daun 7 tertutup oleh 1, dan pada contoh 2, node 4 memiliki anak, tetapi berada di bagian bawah kolom 0.
Mengurutkan kolom sebagai teks. Sebagai string, "-10" berada di antara "-1" dan "-2".

Pertanyaan yang sering diajukan3

Apa itu tampilan bawah dari pohon biner?

Beri kolom akar nilai 0, setiap langkah ke kiri satu kolom lebih sedikit, dan setiap langkah ke kanan satu kolom lebih banyak. Tampilan dari bawah mencantumkan node terdalam di setiap kolom, dari kiri ke kanan. Soal ini memecahkan seri kedalaman berdasarkan urutan level, dengan mempertahankan node yang muncul belakangan.

Berapa kompleksitas waktu untuk tampilan bawah pohon biner?

O(n) untuk n node: breadth-first search menangani setiap node satu kali dengan satu penulisan hash map. Map terurut seperti tree map menambahkan faktor log w untuk w kolom.

Apa perbedaan antara tampilan atas dan tampilan bawah?

Keduanya memilih satu node untuk setiap kolom. Tampilan atas memilih node paling dangkal, sedangkan tampilan bawah memilih node paling dalam. Dalam versi breadth-first, tampilan atas mempertahankan nilai pertama yang diterima suatu kolom, sedangkan tampilan bawah menimpanya setiap kali.

def bottomView(root):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

root = [5, 2, 9, 4, 7, 1, 6]

Output yang diharapkan

[4, 2, 1, 9, 6]