Vertical Order Traversal of a Binary Tree

+10

Pohon biner disimpan dalam array root dengan urutan heap: akar berada pada indeks 0, anak-anak dari indeks i berada di 2*i+1 (kiri) dan 2*i+2 (kanan), -1 menandai posisi kosong, dan array dapat diakhiri dengan entri -1 tambahan.

Akar berada di kolom 0; anak kiri berada satu kolom di sebelah kiri induknya, anak kanan satu kolom di sebelah kanan. Kembalikan satu list untuk setiap kolom, dari kiri ke kanan. Di dalam kolom, urutkan node dari atas ke bawah, dan urutkan node yang berada di kolom dan kedalaman yang sama berdasarkan nilai secara menaik.

Fungsi

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

rootinteger-array: pohon dalam urutan heap, dengan -1 untuk posisi kosong
Mengembalikaninteger-2d-array: satu daftar nilai untuk setiap kolom, mulai dari kolom paling kiri, masing-masing dari atas ke bawah

Batasan

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

Contoh

Input: root = [5, 2, 9, 4, 7, 1, 6]
Output: [[4], [2], [5, 1, 7], [9], [6]]
Penjelasan: Kolom 0 menyimpan root 5, lalu 7 dan 1 dua tingkat di bawahnya. Keduanya berada di kolom dan kedalaman yang sama, jadi 1 muncul sebelum 7, meskipun 7 berada lebih ke kiri.

Input: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Output: [[2, 5], [1, 4], [3]]
Penjelasan: Kolom -1 menyimpan 2 pada kedalaman 1 dan 5 pada kedalaman 3 (anak kiri dari 4). Kolom 0 menyimpan akar 1 dan 4 pada indeks 4. Kolom 1 hanya menyimpan 3.

Input: root = [6, -1, -1]
Output: [[6]]
Penjelasan: 6 tidak memiliki anak, jadi jawabannya memiliki satu kolom, [6].

Pertanyaan lanjutan

Setiap nilai paling besar 5000. Bisakah kamu memanfaatkan hal itu untuk menghilangkan pengurutan perbandingan dan menyelesaikannya dalam waktu O(n + 5000)?

Solusi

Setiap node memiliki tiga key: column, depth, dan value. Jawabannya adalah node yang diurutkan berdasarkan key tersebut, satu list untuk setiap column. Jika column dan depth sama, urutkan berdasarkan value, bukan berdasarkan urutan kiri ke kanan saat traversal menemui node tersebut. Jadi, kamu harus mengurutkan semua node sekaligus atau mengurutkan setiap level dalam pencarian breadth-first.

Catat setiap node, lalu urutkan

Intuisi

Kunjungi setiap node sekali, dalam urutan apa pun, lalu catat tripel (kolom, kedalaman, nilai). Langkah menuju child menambah kedalaman sebesar 1 dan menggeser kolom 1 ke kiri atau ke kanan. Lalu urutkan tripel berdasarkan kolom, kedalaman, dan nilai. Node setiap kolom kini berkumpul sesuai urutan yang diperlukan. Telusuri list yang sudah diurutkan, lalu mulai inner list baru setiap kali kolom berubah.

Dalam contoh 1, tripel kolom 0 setelah diurutkan adalah (0, 0, 5), (0, 2, 1), (0, 2, 7). Pengurutan dengan kompleksitas O(n log n) lebih dominan daripada penelusuran O(n), dan tripel membutuhkan ruang O(n).

Algoritma

Masukkan (indeks 0, kolom 0, kedalaman 0) ke stack.
Keluarkan sebuah node, catat (kolom, kedalaman, nilai), lalu masukkan setiap child yang nyata dengan kolom col-1 atau col+1 dan kedalaman depth+1.
Saat stack kosong, urutkan tuple berdasarkan kolom, lalu kedalaman, kemudian nilai.
Telusuri tuple tersebut, mulai list baru setiap kali kolom berubah.

def verticalTraversal(root):
    n = len(root)
    entries = []  # (column, depth, value) for every node
    stack = [(0, 0, 0)]  # (node index, column, depth); the root is never empty
    while stack:
        i, col, depth = stack.pop()
        entries.append((col, depth, root[i]))
        for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
            if child < n and root[child] != -1:
                stack.append((child, child_col, depth + 1))
    # Column, then depth, then value: exactly the order of the answer.
    entries.sort()
    result = []
    for k, (col, depth, value) in enumerate(entries):
        if k == 0 or col != entries[k - 1][0]:
            result.append([])  # a new column starts
        result[-1].append(value)
    return result

Urutkan di dalam setiap level, satu level demi satu level

Intuisi

Penelusuran breadth-first menangani satu level sekaligus. Jika setiap node menambahkan nilainya ke list kolomnya saat ditangani, setiap list sudah tersusun dari atas ke bawah, jadi kedalaman tidak perlu diurutkan. Kesamaan hanya terjadi dalam satu level, jadi urutkan setiap level berdasarkan kolom, lalu nilai, sebelum menanganinya.

Dalam contoh 1, level 2 tiba sebagai 4, 7, 1, 6 di kolom -2, 0, 0, 2 dan diurutkan menjadi 4, 1, 7, 6, sehingga kolom 0 menjadi [5, 1, 7]. Kolom-kolom yang terisi membentuk rentang berkesinambungan, jadi melacak nilai terkecil dan terbesar sudah cukup.

Mengurutkan level yang terdiri dari m node membutuhkan biaya O(m log m). Kasus terburuk tetap O(n log n), karena level terakhir dari pohon penuh berisi sekitar setengah dari seluruh node. Ruang yang dibutuhkan adalah O(n).

Algoritma

Mulai dengan sebuah level yang berisi (indeks 0, kolom 0).
Urutkan level berdasarkan kolom, lalu nilai.
Sesuai urutan tersebut, tambahkan setiap nilai ke list kolomnya, lalu kumpulkan anak aslinya, dengan kolom col-1 dan col+1, ke level berikutnya.
Ulangi sampai sebuah level kosong, sambil melacak kolom terkecil dan terbesar.
Kembalikan list dari kolom terkecil hingga terbesar.

def verticalTraversal(root):
    n = len(root)
    columns = {}  # column -> its values, top to bottom
    level = [(0, 0)]  # (node index, column) of every node on the current level
    while level:
        # Every node here has the same depth: order them by column, then value.
        level.sort(key=lambda node: (node[1], root[node[0]]))
        next_level = []
        for i, col in level:
            columns.setdefault(col, []).append(root[i])
            for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
                if child < n and root[child] != -1:
                    next_level.append((child, child_col))
        level = next_level
    # The columns that hold a node form one unbroken range.
    return [columns[col] for col in range(min(columns), max(columns) + 1)]

Jebakan dan kasus tepi

Membiarkan nilai yang sama tetap dalam urutan dari kiri ke kanan. Breadth-first search tanpa pengurutan per tingkat menghasilkan [5, 7, 1] untuk kolom 0 pada contoh 1, bukan [5, 1, 7].
Menambahkan nilai saat menelusuri secara depth-first tanpa pengurutan. Dalam [1, 2, 3, -1, 4, -1, -1, -1, -1, -1, 5], penelusuran yang mendahulukan kiri menambahkan 5 (kedalaman 3) ke kolom 1 sebelum 3 (kedalaman 1).
Mengurutkan berdasarkan kolom dan nilai, tetapi tidak berdasarkan kedalaman. Kolom 0 pada contoh 1 kemudian menjadi [1, 5, 7].
Menjadikan kolom sebagai kunci string. Jika diurutkan sebagai teks, "-1" berada sebelum "-2", sehingga kolom di sebelah kiri 0 berada dalam urutan yang salah.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu penelusuran urutan vertikal pada pohon biner?

Mengurutkan semua node berdasarkan kolom, kedalaman, dan nilai membutuhkan biaya O(n log n) dan mendominasi penelusuran O(n). Mengurutkan per tingkat memiliki kasus terburuk yang sama, karena tingkat terakhir dari pohon penuh menampung sekitar setengah dari jumlah node. Ruang yang dibutuhkan adalah O(n).

Apakah traversal berdasarkan urutan vertikal dapat dilakukan tanpa pengurutan?

Hanya jika nilai yang sama diurutkan dari kiri ke kanan. Kemudian, breadth-first search yang menambahkan setiap nilai ke list kolomnya akan menghasilkan jawaban dalam O(n). Jika nilai yang sama diurutkan berdasarkan nilai, kamu memerlukan pengurutan, tetapi hanya dalam satu level, karena hanya node pada level yang sama yang bisa memiliki nilai yang sama.

Bagaimana traversal urutan vertikal berkaitan dengan tampilan atas dan tampilan bawah?

Ketiganya mengelompokkan node berdasarkan nomor kolom yang sama. Tampilan atas mempertahankan node paling dangkal di setiap kolom, sedangkan tampilan bawah mempertahankan node paling dalam. Traversal urutan vertikal mempertahankan setiap node, dan jika beberapa node berada pada level yang sama, traversal mengurutkannya berdasarkan nilai, sedangkan kedua tampilan memilih node berdasarkan posisinya.

def verticalTraversal(root):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

root = [5, 2, 9, 4, 7, 1, 6]

Output yang diharapkan

[[4], [2], [5, 1, 7], [9], [6]]