Construct Binary Tree from Preorder and Inorder Traversal

Q: Mengapa kamu memerlukan preorder dan inorder untuk membangun kembali pohon biner?

Preorder saja tidak menentukan bentuknya. Preorder [1, 2] cocok dengan pohon yang 2 menjadi anak kiri 1 dan pohon yang 2 menjadi anak kanannya. Inorder memastikan bentuknya: [2, 1] menempatkan 2 di kiri, sedangkan [1, 2] menempatkannya di kanan. Dengan nilai yang berbeda, pasangan tersebut menjelaskan tepat satu pohon.

Q: Bisakah kamu membangun kembali pohon biner dari traversal preorder dan postorder?

Tidak secara umum. Preorder [1, 2] dan postorder [2, 1] cocok untuk child kiri maupun child kanan, karena kedua traversal tersebut tidak menempatkan root di antara subtree-nya. Pasangan ini hanya cukup untuk pohon biner penuh, yang setiap node-nya memiliki nol atau dua child.

SedangTree traversal Hashing Rekursi

+10

Kamu mendapatkan dua array, preorder dan inorder, yang mencantumkan nilai-nilai berbeda dari pohon biner yang sama. Preorder mengunjungi sebuah simpul, lalu subpohon kirinya, kemudian subpohon kanannya. Inorder mengunjungi subpohon kiri, lalu simpulnya, kemudian subpohon kanan.

Bangun kembali pohon tersebut dan kembalikan sebagai array dalam urutan level: akar pada indeks 0, anak-anak dari indeks i pada 2i+1 (kiri) dan 2i+2 (kanan), serta -1 untuk setiap posisi kosong. Array berakhir pada simpul terakhir, tanpa -1 di akhir.

Fungsi

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: nilai dalam urutan preorder: node, subtree kiri, subtree kanan
inorderinteger-array: nilai dalam urutan inorder: subtree kiri, node, subtree kanan
Mengembalikaninteger-array: pohon dalam urutan level, dengan -1 untuk posisi kosong dan tanpa -1 di akhir

Batasan

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴, dan semua nilainya berbeda.
inorder menyimpan nilai yang sama, dan kedua array menggambarkan pohon biner yang sama.
Kedalaman pohon paling banyak 14, jadi setiap indeks dalam jawaban kurang dari 2¹⁴-1 = 16383.

Contoh

Input: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
Output: [7, 3, 4, 0, 9, -1, 6]
Penjelasan: Preorder dimulai dari akar, 7. Akar ini berada di posisi 3 dalam inorder, jadi 0, 3, 9 berada di kiri dan 4, 6 berada di kanan. 4 hanya memiliki anak kanan, yaitu 6, jadi indeks 5 tetap -1.

Input: preorder = [1, 2, 3]inorder = [2, 3, 1]
Output: [1, 2, -1, -1, 3]
Penjelasan: Akar 1 muncul terakhir di inorder, jadi indeks 2 adalah -1. Dari 2, 3, preorder mencantumkan 2 terlebih dahulu dan inorder menempatkan 3 setelahnya, jadi 3 adalah anak kanannya, pada indeks 4.

Pertanyaan lanjutan

Bisakah kamu membangun kembali pohon tanpa rekursi, dalam satu kali penelusuran preorder dengan stack eksplisit?

Petunjuk

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

0 dari 3 dibuka

Solusi

Preorder memberikan root dari setiap subtree: nilai pertama dalam rentang subtree tersebut. Inorder memberikan pemisah: nilai sebelum root berada di kiri, nilai setelahnya berada di kanan. Rekursi pada kedua bagian membangun kembali tree, dan map dari nilai ke posisi inorder membuat setiap pencarian root hanya membutuhkan satu langkah.

Pisahkan secara rekursif, pindai untuk mencari akar

Intuisi

Dalam preorder, subtree kiri mengikuti root-nya dan menggunakan satu entri untuk setiap nilai, yaitu m-lo entri, dengan m sebagai posisi root dalam inorder. Subtree kanan berada setelahnya, jadi root-nya berada di pre+1+(m-lo). Pada contoh pertama, bagian kiri 0, 3, 9 memiliki tiga nilai, jadi subtree kanan dimulai pada indeks preorder 4, yaitu nilai 4.

Kedalaman paling banyak 14 memastikan setiap indeks output kurang dari 2^14-1. Isi sebanyak itu sel dengan -1, tulis setiap nilai pada indeksnya, lalu hapus entri -1 di bagian akhir.

Memindai setiap rentang inorder untuk mencari root-nya membutuhkan biaya O(n·h): rentang pada level yang sama tidak saling tumpang tindih, jadi satu level memindai paling banyak n entri, paling banyak 14 × 3000 = 42000 langkah di sini. Tanpa batas kedalaman, tree yang berbentuk seperti jalur membuatnya menjadi O(n²).

Algoritma

Buat out dengan 2^14-1 entri, semuanya -1.
Tulis build(pre, lo, hi, h): jika lo > hi, kembalilah. Jika tidak, tulis preorder[pre] ke out[h].
Pindai inorder dari lo untuk menemukan posisi akar m. Subpohon kiri memiliki m-lo nilai.
Panggil build(pre+1, lo, m-1, 2*h+1) dan build(pre+1+(m-lo), m+1, hi, 2*h+2).
Panggil build(0, 0, n-1, 0), lalu hapus entri -1 di bagian akhir dan kembalikan sisanya.

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

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

Belah secara rekursif dengan peta posisi

Intuisi

Nilainya berbeda, jadi setiap nilai memiliki tepat satu posisi di inorder. Catat posisi tersebut dalam map yang memetakan nilai ke posisi sebelum rekursi dimulai, sehingga setiap pencarian root hanya membutuhkan satu langkah.

Membangun map membutuhkan O(n), lalu setiap nilai ditempatkan satu kali dengan pekerjaan konstan, sehingga total waktunya O(n). Map membutuhkan ruang O(n), sedangkan rekursi menggunakan satu frame untuk setiap level. Dalam C dan R, nilainya paling besar 10^4, jadi array biasa dengan 10^4+1 entri dapat digunakan sebagai map.

Algoritma

Buat map dari setiap nilai inorder ke posisinya.
Buat out dengan 2^14-1 entri, semuanya -1.
Di build(pre, lo, hi, h), kembalikan jika lo > hi; jika tidak, tulis preorder[pre] ke out[h] dan cari posisinya m di map.
Lakukan rekursi dengan build(pre+1, lo, m-1, 2*h+1) dan build(pre+1+(m-lo), m+1, hi, 2*h+2).
Panggil build(0, 0, n-1, 0), lalu buang entri -1 di bagian akhir dan kembalikan sisanya.

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

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

Jebakan dan kasus tepi

Memulai subtree kanan pada pre+1+m, bukan pre+1+(m-lo). Cara ini berhasil saat lo bernilai 0, seperti pada pemanggilan teratas, tetapi gagal saat rentang dimulai lebih jauh.
Menghilangkan celah. Anak yang hilang tetap memiliki slotnya, jadi contoh kedua menghasilkan [1, 2, -1, -1, 3], bukan [1, 2, 3].
Membiarkan entri -1 di akhir. Mengembalikan semua 2^14-1 sel membuat contoh pertama memiliki 16376 entri -1 tambahan.
Menyalin irisan kedua array pada setiap pemanggilan, sehingga menambah O(n) untuk setiap level. Teruskan rentang indeks.
Di Lua dan R, array dimulai dari 1. Pertahankan posisi berbasis 0 untuk perhitungan, lalu baca preorder[pre + 1] dan out[h + 1].

Pertanyaan yang sering diajukan3

Mengapa kamu memerlukan preorder dan inorder untuk membangun kembali pohon biner?

Preorder saja tidak menentukan bentuknya. Preorder [1, 2] cocok dengan pohon yang 2 menjadi anak kiri 1 dan pohon yang 2 menjadi anak kanannya. Inorder memastikan bentuknya: [2, 1] menempatkan 2 di kiri, sedangkan [1, 2] menempatkannya di kanan. Dengan nilai yang berbeda, pasangan tersebut menjelaskan tepat satu pohon.

Apa kompleksitas waktu untuk membangun pohon biner dari preorder dan inorder?

Dengan pemetaan dari nilai ke posisi inorder, kompleksitas waktunya O(n) dan ruang tambahan yang dibutuhkan O(n). Tanpa pemetaan, pemindaian setiap rentang inorder untuk mencari root-nya membutuhkan O(n·h), yang menjadi O(n²) pada pohon yang berbentuk seperti jalur.

Bisakah kamu membangun kembali pohon biner dari traversal preorder dan postorder?

Tidak secara umum. Preorder [1, 2] dan postorder [2, 1] cocok untuk child kiri maupun child kanan, karena kedua traversal tersebut tidak menempatkan root di antara subtree-nya. Pasangan ini hanya cukup untuk pohon biner penuh, yang setiap node-nya memiliki nol atau dua child.

def buildTree(preorder, inorder):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

Output yang diharapkan

[7, 3, 4, 0, 9, -1, 6]