Symmetric Tree

+10

Kamu mendapatkan pohon biner yang disimpan dalam array tree dengan urutan level. Akar berada pada indeks 0, anak dari simpul pada indeks i berada pada 2*i+1 (kiri) dan 2*i+2 (kanan), -1 menandai posisi kosong, dan array dapat diakhiri dengan entri -1 tambahan. Kembalikan true jika pohon tersebut merupakan bayangan cermin dari dirinya sendiri terhadap garis vertikal yang melewati akar, dan false jika tidak. Bentuk dan nilainya harus sama-sama cocok.

Fungsi

isSymmetric(tree: integer-array) → boolean

treeinteger-array: pohon biner dalam urutan level, dengan -1 untuk posisi kosong
Mengembalikanboolean: true jika pohon mencerminkan dirinya sendiri, false jika tidak

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 node terakhir.
Kedua anak dari tempat kosong juga kosong, dan kedalamannya paling banyak 14.

Contoh

Input: tree = [1, 2, 2, 3, 4, 4, 3]
Output: true
Penjelasan: Lipat pohon itu menjadi dua bagian. Kedua 2 pada indeks 1 dan 2 bertemu, kedua 3 di bagian luar pada indeks 3 dan 6 bertemu, dan kedua 4 di bagian dalam pada indeks 4 dan 5 bertemu.

Input: tree = [1, 2, 2, -1, 3, -1, 3]
Output: false
Penjelasan: Kedua 3 berada di sebelah kanan induknya. Pada bayangan cermin, anak kanan dari 2 sebelah kiri (indeks 4) berhadapan dengan anak kiri dari 2 sebelah kanan (indeks 5), dan indeks 5 kosong.

Input: tree = [4, 6, 6, 5, -1, -1, 9]
Output: false
Penjelasan: Bentuknya merupakan bayangan cermin: indeks 3 berhadapan dengan indeks 6 dan keduanya memiliki node. Nilainya berbeda, 5 dibandingkan dengan 9, sehingga pohon tersebut tidak simetris.

Pertanyaan lanjutan

Jika bentuknya saling mencerminkan, tetapi beberapa nilainya tidak, berapa nilai node paling sedikit yang harus kamu ubah agar tree menjadi simetris?

Petunjuk

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

0 dari 3 dibuka

Solusi

Setiap simpul memiliki pasangan di posisi cermin di seberang root, dan pasangan dari anak kiri adalah anak kanan. Telusuri kedua sisi secara bersamaan ke arah yang berlawanan, bandingkan bentuk dan nilai pada setiap pasangan, lalu berhenti pada pasangan pertama yang berbeda.

Bandingkan setiap level dengan kebalikannya

Intuisi

Gambar cermin terbaca sama dari kiri ke kanan maupun dari kanan ke kiri, jadi setiap tingkat, termasuk tempat kosongnya, harus terbaca sama dari kedua arah. Pada contoh kedua, tingkat terbawah terbaca -1 3 -1 3, yang jika dibalik menjadi 3 -1 3 -1, jadi jawabannya adalah false.

Tempat kosong harus tetap ada di baris: tanpa tempat kosong tersebut, tingkat itu akan terbaca 3 3 dan dinyatakan benar. Anak dari tempat kosong juga kosong, jadi hanya simpul nyata yang menambahkan entri. Setiap simpul dikunjungi satu kali, dengan waktu O(n), dan hanya satu tingkat yang disimpan di memori pada satu waktu, dengan O(w) untuk tingkat terlebar w.

Algoritma

Mulai dengan list yang berisi indeks akar 0.
Untuk setiap indeks dalam list, dari kiri ke kanan, catat kedua posisi anak: nilai anak jika ada, -1 jika tidak. Kumpulkan anak yang ada untuk tingkat berikutnya.
Jika baris itu berbeda dari kebalikannya, kembalikan false.
Ulangi pada tingkat berikutnya hingga kosong, lalu kembalikan true.

def isSymmetric(tree):
    n = len(tree)
    level = [0]  # the real nodes of one level, left to right
    while level:
        row = []  # the child spots under this level, -1 for an empty one
        next_level = []
        for i in level:
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    row.append(tree[child])
                    next_level.append(child)
                else:
                    row.append(-1)
        if row != row[::-1]:
            return False
        level = next_level
    return True

Rekursi pada pasangan cermin

Intuisi

Bandingkan subtree kiri root pada indeks 1 dengan subtree kanannya pada indeks 2. Dua posisi saling mencerminkan jika keduanya kosong, atau jika keduanya memiliki nilai yang sama dan anak-anaknya saling berseberangan: anak kiri dari satu posisi mencerminkan anak kanan dari posisi lainnya (pasangan luar), dan anak kanan dari satu posisi mencerminkan anak kiri dari posisi lainnya (pasangan dalam). Itulah definisi bayangan cermin yang diterapkan satu tingkat ke bawah, jadi jika setiap pasangan cocok, seluruh pohon juga cocok.

Setiap node nyata termasuk paling banyak dalam satu pasangan, jadi kompleksitas waktunya O(n); kedalaman call stack sama dengan kedalaman pohon, O(h).

Algoritma

Tulis mirrors(a, b). Sebuah posisi kosong jika indeksnya melewati akhir atau berisi -1. Jika kedua posisi kosong, kembalikan true; jika hanya satu yang kosong, kembalikan false.
Jika tree[a] dan tree[b] berbeda, kembalikan false.
Jika tidak, kembalikan mirrors(2*a+1, 2*b+2) dan mirrors(2*a+2, 2*b+1).
Kembalikan mirrors(1, 2). Root tanpa anak menghasilkan dua posisi kosong, yang berarti true.

def isSymmetric(tree):
    n = len(tree)

    def mirrors(a, b):
        # Spots a and b must hold the same value, or both be empty.
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a or empty_b:
            return empty_a and empty_b
        return (tree[a] == tree[b]
                and mirrors(2 * a + 1, 2 * b + 2)   # outer pair
                and mirrors(2 * a + 2, 2 * b + 1))  # inner pair

    return mirrors(1, 2)

Stack eksplisit dari pasangan cerminan

Intuisi

Rekursi hanya mengingat pasangan yang masih menunggu untuk diperiksa, jadi simpan pasangan itu dalam tumpukanmu sendiri. Urutan pemeriksaan tidak penting, karena pohon hanya simetris jika setiap pasangan cocok: tumpukan menghasilkan urutan depth-first, sedangkan antrean menghasilkan urutan per level. Contoh ketiga berhenti pada pasangan pertama yang tidak cocok, (3, 6), yang berisi 5 dan 9.

Setiap node nyata hanya termasuk dalam paling banyak satu pasangan, jadi waktunya adalah O(n). Tumpukan menyimpan sekitar satu pasangan tertunda untuk setiap level pada jalur saat ini, dengan ruang O(h).

Algoritma

Dorong pasangan (1, 2) ke dalam stack.
Ambil pasangan (a, b) dari stack dan uji seperti yang dilakukan mirrors: lewati jika kedua posisi kosong, kembalikan false jika hanya salah satunya yang kosong atau nilainya berbeda.
Jika tidak, dorong (2*a+1, 2*b+2) dan (2*a+2, 2*b+1).
Saat stack kosong, kembalikan true.

def isSymmetric(tree):
    n = len(tree)
    stack = [(1, 2)]  # pairs of spots that must mirror each other
    while stack:
        a, b = stack.pop()
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a and empty_b:
            continue
        if empty_a or empty_b or tree[a] != tree[b]:
            return False
        stack.append((2 * a + 1, 2 * b + 2))  # outer pair
        stack.append((2 * a + 2, 2 * b + 1))  # inner pair
    return True

Jebakan dan kasus tepi

Memeriksa setiap subpohon secara terpisah. Dalam [1, 2, 2, 3, 4, 4, 3], subpohon kiri 2, 3, 4 tidak simetris, tetapi seluruh pohon simetris: subpohon itu harus mencerminkan subpohon kanan.
Memasangkan anak dengan cara yang salah. Pasangannya adalah (2*a+1, 2*b+2) dan (2*a+2, 2*b+1), bukan (2*a+1, 2*b+1).
Hanya membandingkan nilai. Hapus posisi kosong dari [1, 2, 2, -1, 3, -1, 3], lalu setiap tingkat terbaca sama dari kedua arah, tetapi pohonnya tidak simetris.
Membaca melewati akhir. Indeks yang melewati akhir adalah posisi kosong; pohon dengan satu simpul sama sekali tidak memiliki indeks 1 atau 2.
Dalam Lua dan R, array dimulai dari 1: pertahankan indeks simpul berbasis 0 untuk perhitungan 2*i+1 dan baca tree[i + 1].

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Symmetric Tree?

Setiap node nyata dibandingkan satu kali, dalam satu pasangan cermin, sehingga waktunya O(n). Ruang tambahan adalah O(h) untuk versi rekursif dan versi stack, serta O(w), yaitu tingkat terlebar, untuk versi tingkat demi tingkat.

Apa perbedaan antara pohon simetris dan dua pohon yang identik?

Dua pohon identik jika kamu membandingkan bagian kiri dengan bagian kiri dan bagian kanan dengan bagian kanan. Sebuah pohon simetris jika subpohon kirinya merupakan cerminan subpohon kanannya, sehingga perbandingannya bersilang. Pemeriksaan pasangan yang sama menyelesaikan keduanya, dengan pasangan anak yang ditukar.

Apakah pohon dengan satu simpul simetris?

Ya. Dua posisi anaknya yang kosong saling mencerminkan. Sebuah root dengan tepat satu anak tidak pernah simetris, karena anak itu berhadapan dengan posisi yang kosong.

def isSymmetric(tree):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

tree = [1, 2, 2, 3, 4, 4, 3]

Output yang diharapkan

true

Symmetric Tree

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Bandingkan setiap level dengan kebalikannya

Rekursi pada pasangan cermin

Stack eksplisit dari pasangan cerminan

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa