Binary Tree Level Order Traversal

Q: Berapa kompleksitas waktu dari Penelusuran Urutan Level Binary Tree?

Kedua solusi mengunjungi setiap node satu kali: waktu O(n) untuk n node. Jawaban berisi n nilai, jadi ruang yang dibutuhkan adalah O(n) . Selain itu, queue menyimpan sekitar jumlah node di tingkat terlebar, sedangkan rekursi menggunakan ruang sebesar tinggi tree.

Q: Bagaimana kamu tahu di mana satu tingkat berakhir dalam pencarian breadth-first?

Baca ukuran queue di awal setiap putaran, lalu ambil tepat sebanyak itu node. Ada dua cara lain yang juga bisa digunakan: simpan level saat ini dan level berikutnya dalam dua list terpisah, atau masukkan penanda ke dalam queue setelah setiap level.

Q: array sudah disimpan berdasarkan level. Mengapa tidak membacanya per irisan?

Untuk format ini, cara ini berhasil: level d , dengan akar di 0, mengisi indeks 2^d-1 hingga 2^(d+1)-2 , jadi kumpulkan nilai yang tidak kosong dari setiap rentang sampai ada rentang yang tidak berisi nilai. Dalam wawancara, biasanya node object diberikan dengan pointer, dan hanya queue yang tetap digunakan dalam format tersebut.

SedangTree traversal Queue

+10

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

Kembalikan nilai simpul level demi level: satu list untuk setiap level, dari akar hingga level terdalam, masing-masing dengan nilainya dari kiri ke kanan.

Fungsi

levelOrder(tree: integer-array) → integer-2d-array

treeinteger-array: pohon dalam urutan heap, dengan -1 untuk posisi kosong
Mengembalikaninteger-2d-array: satu list nilai untuk setiap level, mulai dari level teratas, masing-masing dari kiri ke kanan

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 tersebut mungkin diakhiri dengan entri -1 tambahan setelah simpul terakhir.
Kedua anak dari posisi kosong juga kosong, dan kedalamannya paling banyak 14.

Contoh

Input: tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
Output: [[4], [9, 2], [6, 8, 5], [3]]
Penjelasan: Indeks 3 kosong, jadi 9 hanya memiliki anak kanan, yaitu 6. Level ketiga terdiri dari 6, 8, 5, dan 3 pada indeks 9, yang berada di bawah 6, sendirian di level keempat.

Input: tree = [7, -1, -1]
Output: [[7]]
Penjelasan: Kedua anak dari root bernilai -1, jadi tree hanya terdiri dari node 7 dan memiliki satu level.

Input: tree = [1, 3, -1, 5, -1, -1, -1]
Output: [[1], [3], [5]]
Penjelasan: Setiap node hanya memiliki anak kiri: 3 pada indeks 1 dan 5 pada indeks 3. Setiap level menyimpan satu nilai, dan entri -1 di bagian akhir tidak menambahkan apa pun.

Pertanyaan lanjutan

Bisakah kamu mengembalikan level dalam urutan zigzag, level pertama dari kiri ke kanan, level kedua dari kanan ke kiri, dan seterusnya, tanpa mengurutkan level mana pun?

Petunjuk

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

0 dari 3 dibuka

Solusi

Setiap level harus dihasilkan sebagai list tersendiri dari kiri ke kanan. Pencarian breadth-first dengan queue mengunjungi simpul dalam urutan tersebut, dan pada awal setiap putaran, queue berisi tepat satu level, jadi ukurannya menunjukkan berapa banyak simpul yang harus diambil. Penelusuran depth-first yang melacak kedalaman setiap simpul juga bisa digunakan.

Kedalaman lebih dahulu, dikelompokkan berdasarkan kedalaman

Intuisi

Telusuri tree secara depth-first, dengan memberikan setiap node kedalamannya, 0 untuk root, dan simpan satu list untuk setiap kedalaman. Node pada kedalaman d menambahkan nilainya ke list d, dengan memulai list tersebut jika ini node pertama yang ditemukan pada levelnya.

Setiap list tersusun dari kiri ke kanan karena penelusuran menyelesaikan subtree kiri sebuah node sebelum memasuki subtree kanannya. Dari dua node pada satu level, node yang jalurnya berbelok ke kiri di titik percabangan akan dicapai lebih dahulu. Pada contoh 1, urutan kunjungan 4, 9, 6, 3, 2, 8, 5 mengisi [4], [9, 2], [6, 8, 5], [3].

Setiap node dikunjungi sekali: waktu O(n), dengan rekursi sedalam tree, paling banyak 14 level.

Algoritma

Buat list level yang kosong.
Kunjungi root dengan kedalaman 0.
Pada node i dengan kedalaman d, berhenti jika i melewati akhir atau tree[i] adalah -1.
Jika hanya ada d list, tambahkan satu list kosong. Tambahkan tree[i] ke list d.
Kunjungi 2i+1, lalu 2i+2, keduanya dengan kedalaman d+1.

def levelOrder(tree):
    n = len(tree)
    levels = []

    def visit(i, depth):
        if i >= n or tree[i] == -1:
            return
        if depth == len(levels):  # the first node seen on this level
            levels.append([])
        levels[depth].append(tree[i])
        # Left before right, so every level fills from left to right.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return levels

Pencarian melebar, satu tingkat setiap putaran

Intuisi

Keluarkan satu node dari antrean dan masukkan anak-anaknya, dimulai dari kiri. Level d+1 hanya masuk saat level d keluar, jadi node keluar level demi level, dari kiri ke kanan.

Untuk membagi aliran itu menjadi beberapa level, baca ukuran antrean di awal putaran. Level sebelumnya sudah habis dan belum ada node dari level berikutnya yang masuk, jadi antrean berisi tepat node-node pada level saat ini. Ambil sebanyak itu node untuk satu baris; anak-anaknya menunggu putaran berikutnya. Pada contoh 1, setiap putaran mengambil 1, 2, 3, lalu 1 node.

Setiap node masuk dan keluar dari antrean satu kali: waktu O(n). Antrean menampung sekitar satu level, paling banyak 8,192 node pada level terdalam dari pohon penuh dengan 14 level.

Algoritma

Masukkan indeks root 0 ke dalam antrean.
Selama antrean tidak kosong, baca ukurannya s dan mulai baris kosong.
Keluarkan s indeks. Untuk setiap indeks i, tambahkan tree[i] ke baris.
Tambahkan 2i+1, lalu 2i+2, ke antrean jika indeks tersebut berada di dalam array dan tidak berisi -1.
Tambahkan baris ke jawaban dan mulai putaran berikutnya.

from collections import deque


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

Jebakan dan kasus tepi

Membaca ukuran queue saat kamu mengosongkannya. Dalam while (j < queue.length), panjangnya bertambah saat anak-anak tiba, sehingga level berikutnya bocor ke baris saat ini.
Menambahkan anak kanan sebelum anak kiri, atau mengunjungi subtree kanan terlebih dahulu. Level kedua pada Contoh 1 kemudian terbaca sebagai [2, 9].
Melewatkan pemeriksaan batas child < n. Anak-anak dari node terdalam berada melewati akhir array.
Menghapus dari bagian depan array list biasa, yang dalam banyak bahasa menggeser seluruh queue setiap kali. Gunakan queue sungguhan atau indeks head.
Menganggap -1 sebagai node. Nilai ini tidak pernah masuk ke baris atau queue: [7, -1, -1] menghasilkan [[7]], bukan [[7], []].

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Penelusuran Urutan Level Binary Tree?

Kedua solusi mengunjungi setiap node satu kali: waktu O(n) untuk n node. Jawaban berisi n nilai, jadi ruang yang dibutuhkan adalah O(n). Selain itu, queue menyimpan sekitar jumlah node di tingkat terlebar, sedangkan rekursi menggunakan ruang sebesar tinggi tree.

Bagaimana kamu tahu di mana satu tingkat berakhir dalam pencarian breadth-first?

Baca ukuran queue di awal setiap putaran, lalu ambil tepat sebanyak itu node. Ada dua cara lain yang juga bisa digunakan: simpan level saat ini dan level berikutnya dalam dua list terpisah, atau masukkan penanda ke dalam queue setelah setiap level.

array sudah disimpan berdasarkan level. Mengapa tidak membacanya per irisan?

Untuk format ini, cara ini berhasil: level d, dengan akar di 0, mengisi indeks 2^d-1 hingga 2^(d+1)-2, jadi kumpulkan nilai yang tidak kosong dari setiap rentang sampai ada rentang yang tidak berisi nilai. Dalam wawancara, biasanya node object diberikan dengan pointer, dan hanya queue yang tetap digunakan dalam format tersebut.

def levelOrder(tree):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]

Output yang diharapkan

[[4], [9, 2], [6, 8, 5], [3]]