Binary Tree Zigzag Level Order Traversal

+10

Kamu mendapatkan binary tree yang disimpan dalam array root. Root berada pada indeks 0, anak-anak dari indeks i berada pada 2*i+1 (kiri) dan 2*i+2 (kanan), -1 menandai posisi kosong, dan array bisa diakhiri dengan entri -1 tambahan.

Kembalikan nilai node per level dalam urutan zigzag: level root dari kiri ke kanan, level berikutnya dari kanan ke kiri, dan seterusnya, bergantian hingga level terdalam. Ini juga disebut traversal level order spiral.

Fungsi

zigzagLevelOrder(root: integer-array) → integer-2d-array

rootinteger-array: pohon dalam urutan heap, dengan -1 untuk posisi kosong
Mengembalikaninteger-2d-array: satu daftar nilai per tingkat, mulai dari tingkat teratas, bergantian dari kiri ke kanan dan dari kanan ke kiri

Batasan

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

Contoh

Input: root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
Output: [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
Penjelasan: Dibaca dari kiri ke kanan, level-levelnya adalah 8; 12, 5; 1, 9, 14; 4, 2, 11. Level 1 dan 3 dibaca dari belakang: [5, 12] dan [11, 2, 4].

Input: root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
Output: [[1], [3, 2], [4, 5, 6, 7]]
Penjelasan: Pohon penuh dengan tiga level: level tengah berbalik menjadi [3, 2] dan level ketiga berjalan dari kiri ke kanan lagi. Dua entri -1 di bagian akhir adalah posisi anak kosong dari 4.

Pertanyaan lanjutan

Bisakah kamu langsung menempatkan setiap nilai di posisi akhirnya dalam barisnya, tanpa membalik urutan dan tanpa stack kedua?

Solusi

Level berasal dari pencarian breadth-first biasa. Bagian barunya adalah arah: setiap level lainnya dihasilkan dalam urutan terbalik. Balik baris ganjil setelah kamu menyusunnya, atau simpan setiap level dalam stack, yang mengembalikan item dalam urutan kebalikan dari urutan saat item dimasukkan.

Urutan level, lalu balikkan setiap level lainnya

Intuisi

Queue yang diproses satu level setiap putaran menghasilkan setiap level dari kiri ke kanan. Beri nomor pada level mulai dari 0 di akar: pola zigzag membaca level ganjil dari kanan ke kiri, jadi membalik tepat baris-baris tersebut menghasilkan jawabannya.

Pencarian mengunjungi setiap node satu kali dan setiap pembalikan menyentuh setiap nilai sekali lagi, jadi waktunya adalah O(n).

Algoritma

Mulai queue dengan indeks 0.
Untuk setiap putaran, simpan panjang queue sebagai s, keluarkan s indeks dari queue ke dalam baris baru, lalu masukkan setiap anak yang sudah ada ke dalam queue, anak kiri sebelum anak kanan.
Jika jawaban sudah berisi jumlah baris ganjil, balik urutan baris tersebut.
Tambahkan baris tersebut dan lanjutkan sampai queue kosong.

from collections import deque


def zigzagLevelOrder(root):
    n = len(root)
    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(root[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
        if len(levels) % 2 == 1:  # levels 1, 3, 5, ... read from right to left
            row.reverse()
        levels.append(row)
    return levels

Dua stack

Intuisi

Simpan level saat ini dalam stack yang di-pop sesuai arah pembacaan level, lalu push anak-anak dari setiap node yang di-pop ke stack kedua. Saat stack saat ini kosong, stack kedua berisi level berikutnya.

Urutan push membuatnya berhasil. Saat pop dari kiri ke kanan, push anak kiri setiap node, lalu anak kanannya: anak kanan dari node paling kanan menjadi yang terakhir di-push, sehingga level berikutnya di-pop dari ujung kanannya. Saat pop dari kanan ke kiri, push anak kanan lalu anak kiri, sehingga anak kiri dari node paling kiri menjadi yang terakhir di-push.

Contoh 1: pop 8, push 12, 5. Pop 5, 12, lalu push 14 dari 5 dan 9, 1 dari 12. Pop 1, 9, 14, lalu push 4, 2 dari 9 dan 11 dari 14. Pop 11, 2, 4.

Setiap node di-push dan di-pop satu kali: waktu O(n), tanpa tahap pembalikan.

Algoritma

Masukkan indeks root 0 ke dalam tumpukan dan mulai membaca dari kiri ke kanan.
Selama tumpukan tidak kosong, keluarkan setiap indeks ke baris baru, lalu masukkan setiap anak yang sudah ada dari node yang dikeluarkan ke dalam tumpukan kedua: kiri lalu kanan saat membaca dari kiri ke kanan, kanan lalu kiri jika tidak.
Tambahkan baris tersebut ke jawaban.
Jadikan tumpukan kedua sebagai tumpukan saat ini, balik arah, lalu ulangi.

def zigzagLevelOrder(root):
    n = len(root)
    levels = []
    current = [0]  # a stack of node indexes; the root is never empty
    left_to_right = True
    while current:
        row = []
        upcoming = []  # the next level, pushed while this one pops
        while current:
            i = current.pop()
            row.append(root[i])
            # Push so that the next level pops out in its own direction.
            if left_to_right:
                children = (2 * i + 1, 2 * i + 2)
            else:
                children = (2 * i + 2, 2 * i + 1)
            for child in children:
                if child < n and root[child] != -1:
                    upcoming.append(child)
        levels.append(row)
        current = upcoming
        left_to_right = not left_to_right
    return levels

Jebakan dan kasus tepi

Membalik urutan simpul anak masuk ke satu antrean. Simpul-simpul saudara bertukar posisi, tetapi urutan simpul induk tetap: level ketiga contoh 1 menghasilkan [9, 1, 14].
Menghitung level mulai dari 1. Setiap pembalikan membuat hasilnya meleset satu level, dan contoh 1 menghasilkan [[8], [12, 5], [14, 9, 1], [4, 2, 11]].
Menggunakan satu urutan push di setiap level pada versi dua stack. Level ketiga contoh 1 lalu menghasilkan [9, 1, 14] saat di-pop.
Melakukan push simpul anak ke stack yang masih kamu gunakan untuk pop. Simpul-simpul itu keluar sebelum simpul lain pada level induknya.
Mengurutkan baris alih-alih membalikkannya. Level terakhir contoh 1 harus berupa [11, 2, 4], yang tidak akan dihasilkan oleh pengurutan apa pun.

Pertanyaan yang sering diajukan3

Apa perbedaan antara penelusuran zigzag dan penelusuran berdasarkan urutan level?

Mereka mengunjungi level yang sama dengan node yang sama. Urutan level membaca setiap level dari kiri ke kanan; urutan zigzag membaca setiap level kedua dari kanan ke kiri, dimulai dari level di bawah root. Keduanya berjalan dalam waktu O(n).

Apakah penelusuran zigzag sama dengan penelusuran spiral pada pohon?

Ya, kedua nama itu menjelaskan penelusuran yang sama. Beberapa teks memulai tingkat kedua dari kiri, bukan dari kanan, sehingga hanya menggeser pembalikan sebanyak satu tingkat. Di sini, tingkat root berjalan dari kiri ke kanan, lalu tingkat berikutnya dari kanan ke kiri.

Dapatkah urutan level zigzag dibuat dengan deque?

Ya. Pertahankan urutan setiap level di deque dari kiri ke kanan. Pada level dari kiri ke kanan, ambil simpul dari depan dan tambahkan anak-anaknya, kiri lalu kanan, ke bagian belakang. Pada level dari kanan ke kiri, ambil simpul dari belakang dan tambahkan anak-anaknya, kanan lalu kiri, ke bagian depan. Jumlah simpul yang kamu ambil saat satu putaran dimulai tetap menandai level tersebut.

def zigzagLevelOrder(root):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]

Output yang diharapkan

[[8], [5, 12], [1, 9, 14], [11, 2, 4]]