Subtree of Another Tree

Q: Berapa kompleksitas waktu dari Subtree of Another Tree?

Membandingkan dari setiap node membutuhkan biaya O(n·m) dalam kasus terburuk, dengan n dan m sebagai ukuran kedua pohon. Membandingkan hanya pada node yang tingginya sama dengan tinggi subRoot mengurangi biayanya menjadi O(n + m) , karena setiap node root kemudian ditelusuri paling banyak satu kali.

Q: Bisakah Subtree of Another Tree diselesaikan dengan pencocokan string?

Ya. Tuliskan setiap pohon dalam urutan pre-order dengan # untuk setiap anak kosong dan pemisah sebelum setiap nilai: ,2,1,#,#,3,#,# . subRoot adalah subtree tepat ketika string-nya muncul di dalam string root , dan KMP menemukannya dalam O(n + m) . Tanpa penanda, bentuk yang berbeda menghasilkan string yang sama; tanpa pemisah, 12 memuat 2 .

MudahTree traversal Rekursi

+10

Kamu mendapatkan dua pohon biner, root dan subRoot, yang masing-masing disimpan dalam sebuah array dengan urutan per level: root berada pada indeks 0, anak-anak dari indeks i berada pada 2*i+1 (kiri) dan 2*i+2 (kanan), dan -1 menunjukkan posisi kosong. Sebuah array mungkin diakhiri dengan entri -1 tambahan.

Kembalikan true jika ada node pada root, beserta semua turunannya, yang bentuk dan nilainya sama persis dengan subRoot, dan false jika tidak. Seluruh root juga dihitung.

Fungsi

isSubtree(root: integer-array, subRoot: integer-array) → boolean

rootinteger-array: pohon yang akan dicari, dalam urutan level dengan -1 untuk posisi kosong
subRootinteger-array: pohon yang harus dicari, dalam format yang sama
Mengembalikanboolean: true jika subRoot muncul di root sebagai node dengan semua turunannya, false jika tidak

Batasan

1 ≤ root.length ≤ 32767 dan 1 ≤ subRoot.length ≤ 32767
Setiap entri adalah -1 atau nilai dari 0 hingga 10⁴.
root[0] dan subRoot[0] tidak pernah bernilai -1, jadi kedua pohon memiliki setidaknya satu simpul.
Salah satu array dapat diakhiri dengan entri -1 tambahan setelah node terakhirnya.
Kedua anak dari posisi kosong juga kosong, dan setiap pohon memiliki kedalaman paling banyak 14.
Nilai dapat berulang.

Contoh

Input: root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
Output: true
Penjelasan: Node 2 pada indeks 1 memiliki anak 1 dan 3, dan keduanya adalah daun. Itulah tepatnya subRoot.

Input: root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
Output: false
Penjelasan: 3 di bawah node 2 sekarang memiliki anak 0. Sebuah subtree mencakup semua descendant, jadi node 2 mencakup empat node, sedangkan subRoot memiliki tiga node, dan tidak ada node lain yang memiliki 2.

Input: root = [5, 5, 7]subRoot = [5]
Output: true
Penjelasan: Root 5 memiliki dua child, jadi tidak cocok dengan node tunggal 5. 5 pada indeks 1 adalah leaf dan cocok.

Pertanyaan lanjutan

Bisakah kamu membuat sidik jari setiap subtree dari nilainya dan sidik jari anak-anaknya, sehingga perbandingan dengan subRoot membutuhkan biaya O(1)? Apa yang kamu lakukan ketika dua subtree yang berbeda menghasilkan sidik jari yang sama?

Petunjuk

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

0 dari 3 dibuka

Solusi

Masalah ini memiliki dua bagian: menentukan apakah dua pohon identik, dan memilih di bagian mana dalam root pemeriksaan itu dijalankan. Hanya node yang tingginya sama dengan tinggi subRoot yang dapat cocok, dan node dengan tinggi yang sama tidak pernah tumpang tindih, jadi pemeriksaan hanya pada node tersebut akan mengunjungi setiap node root paling banyak satu kali.

Bandingkan di setiap node

Intuisi

Sebuah posisi i valid jika i berada di dalam array dan nilai di sana bukan -1. Dua pohon identik jika keduanya kosong, atau jika puncaknya menyimpan nilai yang sama dan subpohon kiri serta subpohon kanannya identik. same(i, j) menelusuri root dari i dan subRoot dari j secara bersamaan. Jika subRoot muncul di root, puncaknya berada pada suatu node, jadi coba same(i, 0) dari setiap i yang valid.

Kecocokan yang hampir sempurna dapat berjalan hingga m langkah sebelum gagal, dari masing-masing n node: O(n·m). Di sini, batas kedalaman membatasinya: sebuah node hanya ditelusuri oleh pemeriksaan yang dimulai dari node itu atau di atasnya, paling banyak 14 kali.

Algoritma

Tulis same(i, j). Jika posisi i di root dan posisi j di subRoot sama-sama kosong, kembalikan true; jika hanya salah satunya yang kosong, kembalikan false.
Jika kedua nilainya berbeda, kembalikan false. Jika tidak, kembalikan same(2*i+1, 2*j+1) dan same(2*i+2, 2*j+2).
Kembalikan true jika same(i, 0) berlaku untuk suatu indeks nyata i dari root, dan false jika tidak.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    # Try every real node of root as the top of a match.
    for i in range(n):
        if root[i] != -1 and same(i, 0):
            return True
    return False

Bandingkan hanya jika tingginya sama

Intuisi

Pohon yang identik memiliki tinggi yang sama, dihitung berdasarkan jumlah node pada jalur terpanjang ke bawah. Jadi, hanya node root yang tingginya sama dengan tinggi subRoot yang perlu diperiksa. Pada contoh pertama, tinggi subRoot adalah 2, dan di root, hanya node 2 dan 8 yang memiliki tinggi tersebut.

Sebuah node lebih tinggi daripada setiap node di bawahnya, jadi dua node dengan tinggi yang sama tidak pernah berada satu di dalam yang lain. Setiap pemeriksaan hanya menelusuri subtree dari node awalnya, jadi secara keseluruhan pemeriksaan tersebut menelusuri setiap node root paling banyak satu kali.

Indeks anak selalu lebih besar daripada indeks induknya, jadi pemindaian dari indeks terakhir ke awal akan mencapai kedua anak sebelum induknya. Kedua pemindaian tinggi dan pemeriksaan membutuhkan waktu O(n + m).

Algoritma

Isi array tinggi untuk setiap tree, telusuri dari indeks terakhir hingga 0: tempat kosong mendapat nilai 0, node yang ada mendapat 1 ditambah tinggi yang lebih besar dari kedua anaknya.
Untuk setiap indeks i pada root yang tingginya sama dengan tinggi pada indeks 0 dari subRoot, jalankan same(i, 0) dan kembalikan true jika kondisi tersebut terpenuhi.
Kembalikan false.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    def heights(tree):
        # Children sit at larger indexes, so a backward scan finishes them first.
        h = [0] * len(tree)
        for i in range(len(tree) - 1, -1, -1):
            if tree[i] != -1:
                left = h[2 * i + 1] if 2 * i + 1 < len(tree) else 0
                right = h[2 * i + 2] if 2 * i + 2 < len(tree) else 0
                h[i] = 1 + max(left, right)
        return h

    target = heights(subRoot)[0]
    rootHeights = heights(root)
    # Only a node of the same height can match, and no two such nodes overlap.
    for i in range(n):
        if rootHeights[i] == target and same(i, 0):
            return True
    return False

Jebakan dan kasus tepi

Menerima kecocokan parsial, seperti pada contoh kedua. same harus gagal saat root memiliki node di posisi yang kosong pada subRoot.
Berhenti pada node pertama dengan nilai yang tepat. Pada contoh ketiga, 5 di root tidak cocok, sedangkan leaf 5 di bawahnya cocok.
Membandingkan irisan dari kedua array. Node subtree tersebar di banyak level, dan salah satu array bisa diakhiri dengan entri -1 tambahan. Indeks yang melewati akhir array adalah posisi kosong, seperti -1.
Di Lua dan R, pertahankan indeks node berbasis 0 untuk perhitungan 2*i+1, lalu baca root[i + 1].

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Subtree of Another Tree?

Membandingkan dari setiap node membutuhkan biaya O(n·m) dalam kasus terburuk, dengan n dan m sebagai ukuran kedua pohon. Membandingkan hanya pada node yang tingginya sama dengan tinggi subRoot mengurangi biayanya menjadi O(n + m), karena setiap node root kemudian ditelusuri paling banyak satu kali.

Bisakah Subtree of Another Tree diselesaikan dengan pencocokan string?

Ya. Tuliskan setiap pohon dalam urutan pre-order dengan # untuk setiap anak kosong dan pemisah sebelum setiap nilai: ,2,1,#,#,3,#,#. subRoot adalah subtree tepat ketika string-nya muncul di dalam string root, dan KMP menemukannya dalam O(n + m). Tanpa penanda, bentuk yang berbeda menghasilkan string yang sama; tanpa pemisah, 12 memuat 2.

Apakah node yang cocok dengan subRoot tetapi memiliki anak tambahan tetap dihitung?

Tidak. Subtree adalah node beserta semua turunannya, jadi setiap node di bawah node yang cocok juga harus muncul di subRoot. Pada contoh kedua, tambahan 0 di bawah 3 membuat jawabannya false.

def isSubtree(root, subRoot):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

root = [6, 2, 8, 1, 3, -1, 9]
subRoot = [2, 1, 3]

Output yang diharapkan

true