Invert Binary Tree

Q: Apa kompleksitas waktu untuk membalik pohon biner?

Setiap node dikunjungi sekali, jadi kompleksitas waktunya O(n) . Rekursi menggunakan ruang stack O(h) untuk tree dengan kedalaman h , dan queue menggunakan O(w) untuk level terlebar. Dalam versi array ini, hasilnya berupa array baru, yang menambahkan O(n) .

MudahTree traversal

+10

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

Balikkan tree: tukar anak kiri dan kanan setiap node agar seluruh tree menjadi bayangan cerminnya. Kembalikan tree yang sudah dibalik dalam bentuk yang sama, tanpa entri -1 di bagian akhir.

Fungsi

invertTree(tree: integer-array) → integer-array

treeinteger-array: pohon biner dalam urutan level, dengan -1 untuk posisi kosong
Mengembalikaninteger-array: pohon hasil pencerminan dalam urutan level, tanpa entri -1 di bagian akhir

Batasan

1 ≤ tree.length ≤ 16383
Setiap tree[i] adalah -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 node terakhir.
Kedua anak dari tempat kosong juga kosong, dan kedalamannya paling banyak 14.

Contoh

Input: tree = [5, 3, 8, 1, 4, -1, 9]
Output: [5, 8, 3, 9, -1, 4, 1]
Penjelasan: Anak-anak root 3 dan 8 bertukar tempat. Di bawahnya, 1 dan 4 yang berada di bawah 3 kembali sebagai 4 dan 1, dan 8, yang sebelumnya hanya memiliki anak kanan 9, kini memiliki anak itu di sebelah kirinya.

Input: tree = [2, 7, -1, 6]
Output: [2, -1, 7, -1, -1, -1, 6]
Penjelasan: Rangkaian 2, 7, 6 condong ke kiri, jadi bayangannya condong ke kanan: 7 berpindah dari indeks 1 ke 2 dan 6 dari 3 ke 6. Jawabannya lebih panjang daripada input.

Input: tree = [1, -1, -1]
Output: [1]
Penjelasan: Satu node merupakan cermin bagi dirinya sendiri. Dua entri -1 adalah padding, dan jawaban menghapus setiap -1 di akhir.

Pertanyaan lanjutan

Bagaimana cara memeriksa apakah sebuah pohon merupakan cerminan dirinya sendiri dengan menggunakan pasangan indeks yang sama, tetapi tanpa membuat salinan terbalik?

Petunjuk

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

0 dari 3 dibuka

Solusi

Pencerminan menukar subtree kiri dan kanan dari setiap node. Di sini, posisi node adalah indeksnya, jadi menukar dua subtree memindahkan setiap node di dalamnya. Sebagai gantinya, susun jawaban dalam array baru dengan membawa sepasang indeks selama traversal: posisi node saat ini dan posisi cerminnya.

Rekursi yang menempatkan setiap simpul pada indeks cerminnya

Intuisi

Akar tetap berada pada indeks 0. Subpohon kiri sebuah simpul menjadi subpohon kanan dari salinan cerminnya, jadi jika simpul pada src berada di dst, anak kirinya berada di 2*dst+2 dan anak kanannya berada di 2*dst+1. Dengan begitu, kita mendapatkan place(src, dst), yang menyalin satu nilai lalu melakukan rekursi pada kedua anak dengan tujuan yang ditukar. Pada contoh pertama, 3 pada indeks 1 berada di 2, jadi anak-anaknya, 1 dan 4, berada di 6 dan 5.

Sebuah simpul tidak pernah berpindah level, tetapi indeks cerminnya bisa berada melewati akhir input. Tentukan ukuran output hingga mencakup level penuh (1, 3, 7, 15, ...): pada contoh kedua, panjang 4 menjadi 7, sehingga tersedia ruang untuk 6 pada indeks 6. Setiap simpul ditempatkan satu kali, jadi kompleksitas waktunya O(n), dengan output berukuran O(n) dan tumpukan pemanggilan paling banyak 14 frame.

Algoritma

Bulatkan panjang ke atas menjadi size = 2^k - 1 dan isi output berukuran tersebut dengan -1.
Tulis place(src, dst): jika src melewati akhir atau tree[src] adalah -1, kembalikan.
Jika tidak, tetapkan out[dst] = tree[src], lalu panggil place(2*src+1, 2*dst+2) dan place(2*src+2, 2*dst+1).
Panggil place(0, 0), hapus entri -1 di bagian akhir, lalu kembalikan output.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

    place(0, 0)
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Pencarian melebar dengan antrean pasangan indeks

Intuisi

Pasangan yang sama juga berfungsi dengan queue. Mulai dengan (0, 0); setiap pasangan yang kamu keluarkan menyalin satu nilai dan memasukkan setiap anak yang ada ke queue dengan tujuan yang ditukar. Penukaran ditulis ke indeks tujuan, karena array tidak dapat menukar dua subtree dalam satu langkah. Setiap node yang ada masuk ke queue satu kali, dengan membawa posisi tempatnya seharusnya.

Waktunya O(n), dan queue menampung O(w) pasangan untuk level terlebar w. Tidak ada call stack yang dapat mengalami overflow.

Algoritma

Bulatkan panjang ke atas hingga mencapai level utuh dan isi output dengan ukuran tersebut menggunakan -1.
Masukkan pasangan (0, 0) ke dalam antrean.
Ambil pasangan (src, dst) dari bagian depan antrean dan tetapkan out[dst] = tree[src].
Masukkan (2*src+1, 2*dst+2) dan (2*src+2, 2*dst+1) ke dalam antrean untuk setiap anak yang berada di dalam array dan bukan -1.
Saat antrean kosong, buang entri -1 di bagian akhir dan kembalikan output.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Jebakan dan kasus tepi

Menukar tree[2*i+1] dan tree[2*i+2] secara langsung. Itu menukar dua nilai, bukan subtree-nya: pada contoh pertama, 1 dan 4 tetap berada di bawah 8.
Membuat output sepanjang input. 6 pada contoh kedua berada setelah indeks terakhir input.
Lupa menghapus entri -1 di bagian akhir, baik untuk input yang ditambah padding maupun untuk mirror yang berakhir lebih awal daripada input.
Di Lua dan R, lupa bahwa indeks array dimulai dari 1. Pertahankan indeks mulai dari 0 untuk aritmetika 2*i+1 dan baca tree[i + 1].

Pertanyaan yang sering diajukan3

Apa arti membalik binary tree?

Membalik binary tree mengubahnya menjadi bayangan cerminnya: di setiap node, subtree kiri dan kanan bertukar tempat. Root tetap di tempatnya, dan rantai kiri menjadi rantai kanan. Membaliknya dua kali akan mengembalikan tree ke bentuk semula.

Apa kompleksitas waktu untuk membalik pohon biner?

Setiap node dikunjungi sekali, jadi kompleksitas waktunya O(n). Rekursi menggunakan ruang stack O(h) untuk tree dengan kedalaman h, dan queue menggunakan O(w) untuk level terlebar. Dalam versi array ini, hasilnya berupa array baru, yang menambahkan O(n).

Mengapa membalik pohon biner membalik urutan setiap tingkat?

Pencerminan membalik sisi kiri dan kanan di semua bagian, sehingga simpul pada setiap tingkat muncul dalam urutan yang berlawanan. Dalam urutan tingkat, potongan setiap tingkat dibalik: potongan [1, 4, -1, 9] menjadi [9, -1, 4, 1]. Membalik setiap tingkat setelah mengisi tingkat terakhir dengan -1 adalah solusi ketiga berkompleksitas O(n) untuk tata letak ini.

def invertTree(tree):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

[5, 8, 3, 9, -1, 4, 1]