Top View of Binary Tree

Q: Berapa kompleksitas waktu untuk tampilan atas pohon biner?

Pencarian breadth-first mengunjungi setiap node n satu kali dengan pencarian map O(1) per node, sehingga berjalan dalam waktu O(n) jika kamu melacak kolom terkecil dan terbesar. Map kolom yang terurut membuat kompleksitasnya menjadi O(n log w) untuk w kolom.

SedangTree traversal Hashing

+10

Kamu mendapatkan pohon biner yang disimpan dalam array root dengan urutan heap: root berada di indeks 0, anak-anak dari indeks i berada di 2*i+1 (kiri) dan 2*i+2 (kanan), dan -1 menandakan tempat kosong.

Root berada di kolom 0; anak kiri berada satu kolom di sebelah kiri induknya dan anak kanan berada satu kolom di sebelah kanan. Jika dilihat dari atas, kamu melihat node paling dangkal di setiap kolom; jika ada nilai yang sama, pilih node yang lebih dahulu dalam levelnya dari kiri ke kanan (indeks yang lebih kecil). Kembalikan nilai-nilai yang terlihat, dari kolom paling kiri hingga paling kanan.

Fungsi

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

rootinteger-array: pohon dalam urutan heap, dengan -1 untuk posisi kosong
Mengembalikaninteger-array: nilai yang terlihat dari atas di setiap kolom, mulai 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 tree memiliki setidaknya satu node.
array dapat diakhiri dengan entri -1 tambahan setelah node terakhir.
Kedua anak dari posisi kosong juga kosong, dan pohon memiliki paling banyak 14 tingkat.

Contoh

Input: root = [5, 2, 9, 4, 7, 1, 6]
Output: [4, 2, 5, 9, 6]
Penjelasan: Dari kiri ke kanan, kolom-kolomnya berisi 4 (kolom -2), 2 (-1), akar 5 (0), 9 (1), dan 6 (2). 7 dan 1 juga berada di kolom 0, tetapi akar berada di atasnya.

Input: root = [1, 2, -1, -1, 3, -1, -1, -1, -1, -1, 4]
Output: [2, 1, 4]
Penjelasan: 2 berada di kolom -1. Anak kanannya, 3 pada indeks 4, kembali berada di kolom 0, di bawah root, sehingga tersembunyi. 4 pada indeks 10, anak kanan dari 3, berada sendirian di kolom 1.

Input: root = [6, -1, -1]
Output: [6]
Penjelasan: Indeks 1 dan 2 berisi -1, jadi 6 berada sendiri di kolom 0 dan menjadi seluruh tampilan.

Pertanyaan lanjutan

Dengan object node, bukan array, tidak ada indeks untuk menentukan hasil yang seri. Bagaimana kamu menyatakan aturan untuk hasil seri, dan apakah kode breadth-first-mu berubah?

Solusi

Setiap kolom menampilkan node dengan kedalaman paling dangkal, dan jika kedalamannya sama, node yang muncul lebih dulu dalam urutan level. Urutan ini sama persis dengan urutan node yang dikunjungi oleh pencarian breadth-first, jadi node pertama yang ditemui pencarian dalam suatu kolom adalah jawabannya. Penelusuran depth-first juga bisa digunakan, tetapi harus melacak kedalaman dan menentukan urutan jika terjadi seri dengan cermat.

Penelusuran mendalam, simpul paling dangkal per kolom

Intuisi

Telusuri pohon secara mendalam dengan mencatat kolom dan kedalaman setiap simpul, lalu simpan kedalaman dan nilai simpul terdangkal yang ditemukan sejauh ini untuk setiap kolom.

Ganti hanya jika kedalamannya benar-benar lebih kecil. Dari dua simpul dengan kedalaman sama, simpul yang lebih dulu dalam urutan level akan dicapai lebih dulu oleh penelusuran yang menjelajahi setiap subpohon kiri sebelum subpohon kanan yang bersesuaian, karena saat kedua jalur bercabang, penelusuran bergerak ke kiri. Jika penggantian dilakukan pada kedalaman yang sama, simpul yang lebih akhir akan menang: dengan indeks 3 kosong dan simpul pada indeks 19 dan 23, keduanya berada di kolom -2 pada kedalaman 4, dan jawabannya adalah simpul pada indeks 19.

Kolom yang terisi membentuk rentang berurutan, karena simpul di kolom -3 memiliki leluhur di kolom -1 dan -2, jadi catat kolom terkecil dan terbesar. Setiap simpul dikunjungi sekali, waktu O(n), dan rekursinya memiliki kedalaman sekitar h pemanggilan.

Algoritma

Kunjungi akar dengan kolom 0 dan kedalaman 0. Segera kembali jika indeks berada di luar array atau berisi -1.
Jika kolom belum memiliki node, atau kedalaman ini lebih kecil dari kedalaman yang tersimpan, simpan kedalaman dan nilainya.
Kunjungi 2i+1 dengan kolom col-1, lalu 2i+2 dengan kolom col+1, satu tingkat lebih dalam.
Kembalikan nilai yang tersimpan dari kolom terkecil hingga terbesar.

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

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace only on a strictly smaller depth: on a tie, the node
        # met first is the one further left, which comes first 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)]

Pencarian melebar lebih dahulu, node pertama per kolom

Intuisi

Queue yang mengambil root, lalu child kiri setiap node dan kemudian child kanannya, mengeluarkan node dalam urutan level: setiap node dengan kedalaman d sebelum node mana pun dengan kedalaman d+1, dan setiap level dari kiri ke kanan. Itulah prioritas masalah ini, jadi node pertama yang diterima sebuah kolom adalah node yang terlihat dari atas, dan setiap node berikutnya dilewati.

Setiap node memerlukan satu pencarian map, totalnya O(n). Queue dapat menampung satu level penuh, hingga sekitar setengah dari jumlah node, sehingga penggunaan ruangnya O(n).

Algoritma

Masukkan pasangan (indeks 0, kolom 0) ke dalam antrean.
Ambil pasangan (i, col). Jika map tidak memiliki entri untuk col, simpan root[i] di sana.
Tambahkan (2i+1, col-1), lalu (2i+2, col+1), untuk setiap anak yang ada.
Saat antrean kosong, kembalikan nilai-nilai map dari kolom terkecil hingga terbesar.

from collections import deque


def topView(root):
    n = len(root)
    top = {}  # column -> value of the first 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 shallower nodes first, and left before right
        # on one level, so the first node of a column is the one seen from above.
        if col not in top:
            top[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 [top[col] for col in range(min(top), max(top) + 1)]

Jebakan dan kasus tepi

Mempertahankan node pertama yang ditemukan oleh penelusuran depth-first. Jika anak kiri root memiliki anak kanan yang memiliki anak kanan (kolom 1, kedalaman 3), penelusuran akan menemukannya sebelum anak kanan root (kolom 1, kedalaman 1).
Memasukkan anak kanan ke antrean terlebih dahulu: jika terjadi nilai yang sama, node yang dipilih salah.
Mengurutkan kolom sebagai teks: "-1" diurutkan sebelum "-2".
Menganggap subtree kiri mengisi kolom negatif. Pada contoh 2, node 4 berada di subtree kiri root dan di kolom 1.

Pertanyaan yang sering diajukan3

Apa itu tampilan atas dari pohon biner?

Beri nomor pada kolom mulai dari akar dengan angka 0, satu angka lebih kecil untuk anak kiri dan satu angka lebih besar untuk anak kanan. Tampilan atas mencantumkan, untuk setiap kolom dari kiri ke kanan, simpul yang paling dekat dengan akar.

Berapa kompleksitas waktu untuk tampilan atas pohon biner?

Pencarian breadth-first mengunjungi setiap node n satu kali dengan pencarian map O(1) per node, sehingga berjalan dalam waktu O(n) jika kamu melacak kolom terkecil dan terbesar. Map kolom yang terurut membuat kompleksitasnya menjadi O(n log w) untuk w kolom.

Apa perbedaan tampak atas dengan tampak kiri dan tampak bawah?

Tampilan kiri memilih node pertama di setiap tingkat. Tampilan atas memilih node dengan kedalaman paling dangkal di setiap kolom. Tampilan bawah memilih node dengan kedalaman paling dalam di setiap kolom, jadi pencarian breadth-first untuk mendapatkannya menimpa setiap kolom alih-alih menyimpan node pertama.

def topView(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, 5, 9, 6]