Binary Tree Right Side View

Q: Apa kompleksitas waktu dan ruang dari Binary Tree Right Side View?

Waktunya adalah O(n) untuk n node, dan tidak ada solusi yang dapat melewatkan node, karena node paling kanan pada suatu level bisa berada di mana saja. Ruang yang digunakan adalah O(w) untuk antrean, dengan w sebagai lebar level terbesar, atau O(h) untuk penelusuran dari kanan terlebih dahulu pada pohon dengan h level.

SedangTree traversal Queue

+10

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

Lihat pohon dari sisi kanannya. Setiap level menampilkan tepat satu simpul, yaitu yang paling kanan, dan menghalangi simpul lainnya. Daftarkan nilai-nilai tersebut dari level akar hingga level terdalam.

Fungsi

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

rootinteger-array: pohon dalam urutan heap, dengan -1 untuk posisi kosong
Mengembalikaninteger-array: nilai paling kanan di setiap tingkat, mulai dari tingkat teratas

Batasan

1 ≤ root.length ≤ 32767
Setiap root[i] adalah -1 atau nilai dengan 0 ≤ root[i] ≤ 10⁴.
Nilai-nilai node berbeda.
root[0] tidak pernah -1, jadi pohon memiliki setidaknya satu node.
array mungkin diakhiri dengan entri -1 tambahan setelah node terakhir.
Kedua child dari tempat kosong juga kosong, dan tree memiliki paling banyak 14 level.

Contoh

Input: root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
Output: [5, 9, 1, 3]
Penjelasan: Dari sisi kanan, kamu melihat 5, 9, dan 1 (indeks 6). Tingkat keempat hanya berisi 3, pada indeks 8 di bawah 7 dalam subtree kiri. Tidak ada apa pun di sisi kanan yang mencapai kedalaman itu, jadi 3 terlihat.

Input: root = [6, 0, -1, 8, -1, -1, -1]
Output: [6, 0, 8]
Penjelasan: Pohon tersebut merupakan rantai anak kiri: 6, 0, 8. Setiap tingkat berisi satu node, jadi kamu melihat ketiganya, meskipun tidak satu pun merupakan anak kanan.

Input: root = [42]
Output: [42]
Penjelasan: Array dengan panjang 1: root 42 sama sekali tidak memiliki tempat anak, dan tampilan tersebut adalah satu nilai itu.

Pertanyaan lanjutan

Bagaimana cara mendapatkan tampilan sisi kanan pohon yang setiap nodenya dapat memiliki jumlah anak berapa pun, yang disimpan sebagai list dari kiri ke kanan?

Petunjuk

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

0 dari 3 dibuka

Solusi

Kamu melihat node paling kanan di setiap level, dan node itu tidak harus merupakan anak kanan: nilai terakhir pada contoh 1 berada di subtree kiri. Pencarian breadth-first menjadikan node itu sebagai node terakhir di setiap putaran; penelusuran depth-first yang mengunjungi kanan terlebih dahulu akan menemukannya sebelum node lain di levelnya.

Penelusuran melebar, simpul terakhir di setiap tingkat

Intuisi

Proses tree satu level per putaran. Saat putaran dimulai, queue berisi tepat satu level dari kiri ke kanan, jadi indeks terakhir yang kamu keluarkan dari queue pada putaran itu adalah node paling kanan di level tersebut, dan nilainya masuk ke jawaban.

Pada contoh 1, putarannya adalah [5], [2, 9], [7, 4, 1], dan [3], lalu entri terakhirnya menghasilkan 5, 9, 1, 3. Level yang menentukan, bukan sisinya: 3 berada di subtree kiri, tetapi sendirian di levelnya.

Setiap indeks dimasukkan ke queue dan dikeluarkan darinya satu kali, jadi waktunya O(n). Queue dapat membesar hingga selebar level terluas, yaitu O(n) dalam kasus terburuk.

Algoritma

Masukkan indeks root 0 ke dalam queue.
Mulai satu putaran dengan menyimpan panjang queue ke dalam s.
Keluarkan s indeks dari queue. Untuk setiap indeks i, masukkan 2i+1 ke dalam queue, lalu 2i+2 jika nilainya kurang dari panjang array dan bukan -1.
Tambahkan nilai dari indeks terakhir yang dikeluarkan pada putaran tersebut.
Ulangi sampai queue kosong, lalu kembalikan jawabannya.

from collections import deque


def rightSideView(root):
    n = len(root)
    view = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        size = len(queue)  # exactly the nodes of the current level
        for j in range(size):
            i = queue.popleft()
            if j == size - 1:
                view.append(root[i])  # the last node of this level
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
    return view

Penelusuran mendalam, anak kanan terlebih dahulu

Intuisi

Telusuri pohon secara mendalam, coba anak kanan sebelum anak kiri, dan bawa kedalamannya, 0 di akar. Saat penelusuran pertama kali mencapai kedalaman d, jawaban berisi tepat d nilai. Tambahkan nilai node saat itu dan abaikan setiap node berikutnya pada tingkat tersebut.

Node pertama itu adalah yang paling kanan: setiap kali dua jalur menuju suatu tingkat bercabang, penelusuran mengikuti cabang kanan hingga ke dasar sebelum kembali ke cabang kiri. Pada contoh 1, penelusuran mengunjungi 5, 9, 1, 2, 4, 7, 3: penelusuran melewati 2, 4, dan 7, yang tingkatnya sudah memiliki nilai, lalu menambahkan 3.

Setiap node dikunjungi sekali, dengan waktu O(n), dan satu pemanggilan per tingkat di stack, paling banyak 14.

Algoritma

Mulai dengan jawaban kosong dan root pada kedalaman 0.
Lewati indeks yang melewati akhir array atau berisi -1.
Saat panjang jawaban sama dengan kedalaman, tambahkan nilainya: penelusuran telah mencapai level baru, dan mencapainya dari kanan.
Lakukan rekursi ke anak kanan 2i+2 terlebih dahulu, lalu ke anak kiri 2i+1, masing-masing satu level lebih dalam.
Kembalikan jawaban.

def rightSideView(root):
    n = len(root)
    view = []

    def visit(i, depth):
        if i >= n or root[i] == -1:
            return
        if depth == len(view):  # the first node met on this level
            view.append(root[i])
        # Right before left, so the rightmost node of every level comes first.
        visit(2 * i + 2, depth + 1)
        visit(2 * i + 1, depth + 1)

    visit(0, 0)
    return view

Jebakan dan kasus tepi

Hanya mengikuti anak kanan dari root. Contoh 1 menghasilkan [5, 9, 1] dan melewatkan 3; contoh 2 menghasilkan [6].
Membaca slot terakhir di setiap tingkat, root[2^(d+1)-2]. Pada contoh 2, indeks 6 berisi -1; node yang terlihat adalah 8 pada indeks 3.
Melewatkan pemeriksaan panjang pada posisi anak. Pada contoh 1, 3 adalah entri terakhir, jadi posisi anaknya 17 dan 18 tidak ada.
Memasukkan anak kanan ke antrean lebih dahulu sambil menyimpan node terakhir di setiap putaran. Cara ini mengumpulkan tampilan kiri, [5, 2, 7, 3].
Membiarkan node yang muncul belakangan menimpa node sebelumnya saat penelusuran dari kanan lebih dahulu, yang juga menghasilkan tampilan kiri.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dan ruang dari Binary Tree Right Side View?

Waktunya adalah O(n) untuk n node, dan tidak ada solusi yang dapat melewatkan node, karena node paling kanan pada suatu level bisa berada di mana saja. Ruang yang digunakan adalah O(w) untuk antrean, dengan w sebagai lebar level terbesar, atau O(h) untuk penelusuran dari kanan terlebih dahulu pada pohon dengan h level.

Apakah depth-first search yang mendahulukan kiri bisa menyelesaikannya?

Ya, jika kamu menimpa nilai sebelumnya, bukan menyimpannya. Penelusuran dari kiri terlebih dahulu menemukan node di setiap tingkat dari kiri ke kanan, jadi simpan nilai setiap node pada kedalamannya dan biarkan node berikutnya menggantikan nilai sebelumnya. Setiap kedalaman berakhir dengan nilai paling kanan. Kompleksitasnya tetap O(n), tetapi penulisan dilakukan sekali untuk setiap node.

Apakah saya harus menggunakan pencarian breadth-first atau depth-first di sini?

Keduanya bersifat linear. Breadth-first mengikuti definisinya, satu tingkat setiap putaran. Depth-first hanya menyimpan jalur saat ini, sehingga menghemat memori pada pohon yang lebar, dan bentuk rekursifnya beberapa baris lebih pendek.

def rightSideView(root):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

root = [5, 2, 9, 7, 4, -1, 1, -1, 3]

Output yang diharapkan

[5, 9, 1, 3]