Left View of Binary Tree

+10

Kamu mendapatkan pohon biner sebagai array root dalam urutan heap: akar berada di indeks 0, anak dari indeks i berada di 2*i+1 (kiri) dan 2*i+2 (kanan), dan -1 menandai posisi kosong. Array dapat diakhiri dengan entri -1 tambahan.

Berdirilah di sebelah kiri pohon. Pada setiap tingkat, kamu melihat satu simpul, yaitu yang paling kiri; simpul lainnya di tingkat itu tersembunyi di belakangnya. Kembalikan nilai-nilai yang kamu lihat, dari tingkat teratas ke bawah.

Fungsi

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

rootinteger-array: pohon dalam urutan heap, dengan -1 untuk tempat kosong
Mengembalikaninteger-array: nilai paling kiri di setiap level, dimulai dari level teratas

Batasan

1 ≤ root.length ≤ 32767
Setiap root[i] adalah -1 atau nilai dengan 0 ≤ root[i] ≤ 10⁴.
Nilai node berbeda satu sama lain.
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 pohon memiliki paling banyak 14 tingkat.

Contoh

Input: root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
Output: [3, 8, 6, 1]
Penjelasan: 8 adalah leaf, jadi level ketiga dan keempat hanya berisi 6 (indeks 6) dan 1 (indeks 13), keduanya berada di bawah child kanan 5. Kamu tetap melihatnya: [3, 8, 6, 1].

Input: root = [10, -1, -1]
Output: [10]
Penjelasan: Indeks 1 dan 2 berisi -1, jadi 10 tidak memiliki anak dan tampilan hanya menampilkan root.

Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [1, 2, 4]
Penjelasan: Pohon lengkap dengan tiga level. Posisi paling kiri pada setiap level memiliki indeks 0, 1, dan 3, yang menyimpan 1, 2, dan 4.

Pertanyaan lanjutan

Level d mengisi indeks 2^d-1 hingga 2^(d+1)-2. Bisakah kamu membangun tampilan dengan memindai rentang tersebut, tanpa queue atau rekursi? Berapa biayanya pada array yang diberi padding?

Solusi

Mengikuti anak kiri dari root gagal saat subtree kiri lebih pendek: pada contoh pertama, level-level bawah terlihat melalui subtree kanan. Kamu ingin node pertama di setiap level. Breadth-first search memberikan setiap level dari kiri ke kanan; penelusuran depth-first yang mendahulukan kiri akan menemui node paling kiri di setiap level terlebih dahulu.

Penelusuran melebar, simpul pertama di setiap tingkat

Intuisi

Queue yang diproses per putaran memberimu level satu per satu. Di awal putaran, queue berisi tepat satu level, dari kiri ke kanan, karena setiap anak yang ditambahkan selama putaran masuk di belakangnya. Keluarkan indeks sebanyak itu, masukkan anak dari setiap indeks ke queue dengan urutan kiri lebih dahulu, lalu simpan nilai pertama.

Dalam contoh pertama, putarannya adalah [3], [8, 5], [6], dan [1], lalu hasil yang disimpan adalah 3, 8, 6, dan 1. 8 tidak menambahkan apa pun, karena posisi anaknya 3 dan 4 berisi -1.

Setiap node masuk dan keluar dari queue satu kali: waktu O(n). Queue menampung satu level penuh, hingga 8192 indeks pada pohon penuh dengan 14 level.

Algoritma

Mulai perulangan dengan indeks 0 dan jawaban kosong.
Selama perulangan tidak kosong, tetapkan s sebagai ukurannya, lalu keluarkan s indeks. Tambahkan nilai indeks pertama ke jawaban.
Untuk setiap indeks i yang dikeluarkan, masukkan 2i+1, lalu 2i+2 ke perulangan, dengan melewati indeks yang berada di luar batas dan entri yang nilainya sama dengan -1.

from collections import deque


def leftView(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 == 0:
                view.append(root[i])  # the first 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

Kedalaman terlebih dahulu, anak kiri terlebih dahulu

Intuisi

Jelajahi secara depth-first, subtree kiri sebelum subtree kanan, dan teruskan kedalaman setiap node. Node pertama yang dicapai penjelajahan pada kedalaman d adalah node paling kiri di level d. Ambil node paling kiri x pada suatu level dan node mana pun y di sebelah kanannya: pada node terakhir yang sama di jalur mereka, x bergerak ke kiri dan y bergerak ke kanan, lalu penjelajahan menyelesaikan cabang kiri sebelum berbelok ke kanan.

Penjelajahan turun satu level setiap kali, jadi saat pertama kali mencapai kedalaman d, jawaban berisi tepat d nilai. Catat node saat d sama dengan panjang jawaban. Tidak perlu kumpulan kedalaman yang sudah dikunjungi.

Setiap node dikunjungi satu kali, dengan waktu O(n), dan memori menampung satu pemanggilan untuk setiap level, paling banyak 14 di sini. Versi R menggunakan stack-nya sendiri dan memasukkan anak kanan sebelum anak kiri.

Algoritma

Buat jawaban kosong dan panggil visit(0, 0).
Di dalam visit(i, d), segera kembalikan jika i berada di luar array atau root[i] bernilai -1.
Jika d sama dengan panjang jawaban, penelusuran telah mencapai level d untuk pertama kalinya: tambahkan root[i].
Panggil visit(2i+1, d+1), lalu visit(2i+2, d+1).
Kembalikan jawaban setelah pemanggilan pertama selesai.

def leftView(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])
        # Left before right, so the leftmost node of every level comes first.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return view

Jebakan dan kasus tepi

Hanya mengikuti anak kiri dari akar. Pada contoh pertama, penelusuran berhenti di 8 dan melewatkan 6 dan 1.
Membaca slot pertama pada setiap tingkat, root[2^d-1]. Pada contoh pertama, slot pertama tingkat ketiga, indeks 3, berisi -1, sedangkan satu-satunya nodenya berada di indeks 6.
Mengunjungi anak kanan terlebih dahulu dalam penelusuran depth-first. Node pertama yang ditemui pada setiap tingkat kemudian menjadi node paling kanan.
Membaca anak tanpa pemeriksaan batas. 1 pada indeks 13 memiliki posisi anak 27 dan 28, yang berada di luar array dengan 14 entri.

Pertanyaan yang sering diajukan3

Apakah tampilan kiri sama dengan batas kiri sebuah pohon?

Tidak. Batas kiri adalah sebuah jalur: dimulai dari anak kiri root, bergerak ke kiri jika bisa, jika tidak ke kanan, lalu berhenti sebelum leaf. Tampilan kiri mengambil satu node per level dari cabang mana pun. Pada contoh pertama, batasnya kosong karena 8 adalah leaf, tetapi tampilannya menunjukkan 8, 6, dan 1.

Berapa kompleksitas waktu dan ruang dari tampilan kiri?

Kedua solusi mengunjungi setiap node satu kali, jadi waktunya O(n). Queue breadth-first menyimpan satu level penuh, sekitar setengah jumlah node pada tree penuh. Penelusuran dari kiri terlebih dahulu menyimpan satu pemanggilan per level, O(h) untuk h level.

Bagaimana cara mengubah solusi agar tampilan yang benar muncul?

Dalam versi breadth-first, simpan nilai terakhir dari setiap putaran, bukan nilai pertama. Dalam versi depth-first, kunjungi child kanan sebelum child kiri. Dengan begitu, node pertama yang dicapai penelusuran pada setiap level adalah node yang paling kanan.

def leftView(root):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]

Output yang diharapkan

[3, 8, 6, 1]