Temuduga Pengekodan: Bersiri dan Nyahsiri Pokok Perduaan

Masalah dan Konteks yang Berkenaan

Laksanakan dua fungsi untuk pokok perduaan sembarangan:

• serialize(root) menukarkan pokok kepada rentetan.
• deserialize(data) membina semula pokok dengan nilai dan bentuk yang sama.

Andaikan nilai nod ialah integer bertanda 32-bit, pokok mungkin kosong, dan rentetan yang disiri hanya perlu saling kendali dengan penyahsiri ini. Untuk pelaksanaan temuduga secara rekursif, andaikan ketinggian pokok muat dalam had tindanan panggilan (call stack) bahasa tersebut. Penyahsiri di bawah juga menolak teks tidak sah daripada menerima pokok separa secara senyap.

Bagi pokok ini:

1
       / \
      2   3
         / \
        4   5

format yang dipilih ialah:

1,2,#,#,3,4,#,#,5,#,#

Setiap integer merekodkan nod, # merekodkan anak yang tiada, koma memisahkan token, dan preorder menentukan cara token digunakan. Bahan awam yang dikemas kini pada tahun 2026 membentangkan masalah yang sama ini dengan penyelesaian preorder dan level-order, manakala siaran ulangan interviewing.io menunjukkannya ditanya dalam temuduga olok-olok bersama jurutera Meta. Ini menyokongnya sebagai latihan pengekodan wakil semasa tanpa mendakwa bahawa setiap syarikat atau temuduga menggunakannya.

Perkara yang Dinilai oleh Penemuduga

Isyarat pertama ialah sama ada calon mentakrifkan kebolehbalikan sebelum memilih kaedah traversal. Nilai preorder sahaja tidak mencukupi. Punca 1 dengan anak kiri 2 dan punca 1 dengan anak kanan 2 kedua-duanya menghasilkan [1, 2] melainkan anak yang tiada turut dikodkan. Bentuk bertanda mereka berbeza:

Left child:  1,2,#,#,#
Right child: 1,#,2,#,#

Isyarat kedua ialah mereka bentuk pengekod dan penyahsiri sebagai songsangan antara satu sama lain. Dalam preorder, penyahsiri membaca satu token. # melengkapkan subpokok kosong. Sesuatu nilai memulakan nod, selepas itu subpokok lengkap seterusnya adalah milik anak kiri dan subpokok lengkap yang mengikutinya adalah milik anak kanan. Oleh itu, format ini membekalkan sempadan rekursifnya sendiri tanpa menyimpan panjang subpokok.

Isyarat ketiga ialah hujah ketepatan yang kukuh. Bagi pokok dengan n nod, terdapat n + 1 penuding anak null, jadi pengekodan mengandungi tepat 2n + 1 token. Lebih penting lagi, penyahsiri mesti menggunakan tepat token bagi satu subpokok dan meninggalkan lelaran (iterator) pada kedudukan subpokok seterusnya. Aruhan berstruktur membuktikan sifat tersebut.

Akhir sekali, penemuduga mencari sempadan kejuruteraan: input tidak sah, nilai negatif dan pendua, kedalaman rekursi, saiz output, serta masa yang sesuai untuk memilih BFS atau format bersiri pengeluaran.

Soalan Penjelasan Sebelum Menjawab

• Adakah ini pokok perduaan sembarangan atau pokok carian perduaan (BST)? Pokok sembarangan memerlukan penanda

struktur. BST kadangkala boleh dibina semula daripada preorder berserta dasar pendua yang jelas.

• Adakah rentetan mesti mengikut format wayar (wire format) sedia ada? Gesaan ini membenarkan format tersendiri.

Penyimpanan rentas perkhidmatan memerlukan pengversian skema, peraturan keserasian, dan selalunya codec standard.

• Bolehkah nilai nod mengandungi pembatas atau sentinela? Nilai-nilai tersebut adalah integer, jadi koma dan #

adalah tidak samar-samar. Rentetan umum memerlukan pelepasan (escaping) atau awalan panjang.

• Bolehkah pokok itu kosong? Ya. Ia disirikan kepada #.
• Bolehkah input menjadi sangat mendalam atau bersifat bermusuhan (adversarial)? Jawapan rekursif mengandaikan ketinggian terhad.

Pokok yang tidak dipercayai atau sangat condong memerlukan tindanan eksplisit dan had sumber.

• Adakah deserialize hanya akan menerima output yang dipercayai daripada serialize? Kod kekal ketat:

teks kosong, integer tidak sah, pokok terpotong dan token berlebihan di belakang akan ditolak.

• Adakah kita mengoptimumkan untuk keterbacaan atau bait minimum? Teks preorder mudah diterangkan dan diuji.

Protokol binari padat akan mengekodkan tag dan integer secara berbeza.

Rangka Kerja Jawapan 30 Saat

“Saya akan menggunakan traversal preorder dan mengeluarkan # bagi setiap anak yang tiada. Token nilai bermaksud membina nod, kemudian menyahsiri subpokok kiri dan kanannya secara rekursif; # bermaksud mengembalikan None. Penanda null diperlukan kerana nilai sahaja tidak dapat membezakan anak kiri daripada anak kanan. Pengekod dan penyahsiri mencerminkan satu sama lain, dan aruhan berstruktur menunjukkan bahawa setiap panggilan nyahsiri menggunakan tepat satu subpokok. Kedua-dua operasi mengambil masa O(n) dan menghasilkan data O(n), dengan tindanan panggilan O(h) untuk ketinggian h. Saya juga akan menolak input yang terpotong atau berlebihan di hujung dan menyatakan versi lelaran berasaskan BFS atau berasaskan tindanan apabila kedalaman tidak terhad.”

Perincian Langkah demi Langkah

Langkah satu: tolak garis dasar nilai sahaja dengan contoh lawan.

Nilai preorder, inorder, atau postorder sahaja tidak mengenal pasti pokok perduaan sembarangan secara unik. Malah menggabungkan preorder dan inorder menjadi samar-samar apabila nilai pendua dibenarkan. Format mesti mengekodkan bentuk dan juga nilai. Penanda null ialah isyarat bentuk paling mudah untuk format rentetan temuduga.

Langkah dua: pilih tatabahasa yang boleh dinyahsiri dari kiri ke kanan.

Format ini boleh diterangkan secara rekursif:

tree := "#"
      | integer "," tree "," tree

Pelaksanaan sebenar memecahkan token pada koma terlebih dahulu, supaya setiap panggilan rekursif menggunakan satu token dan, bagi sesuatu nilai, dua pengekodan subpokok yang menyusul. Teks integer bertanda tidak pernah mengandungi , atau #. Pokok kosong ialah #; daun dengan nilai 7 ialah 7,#,#.

Tatabahasa ini juga memberikan tak varian (invariant) pengiraan yang berguna. Pokok perduaan dengan n nod sebenar mempunyai n + 1 penuding anak null. Oleh itu, penyirian mengeluarkan n token nilai dan n + 1 token null, menjadikan jumlahnya 2n + 1 token. Kiraan ini adalah diagnostik, bukan pengganti penghuraian: token tidak sah masih boleh mempunyai jumlah ganjil.

Langkah tiga: laksanakan operasi rekursif yang dicerminkan.

from __future__ import annotations

from dataclasses import dataclass


MIN_INT32 = -(2**31)
MAX_INT32 = 2**31 - 1


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None


class Codec:
    NULL = "#"
    SEP = ","

    def serialize(self, root: TreeNode | None) -> str:
        tokens: list[str] = []

        def visit(node: TreeNode | None) -> None:
            if node is None:
                tokens.append(self.NULL)
                return

            if node.val < MIN_INT32 or node.val > MAX_INT32:
                raise ValueError("node value is outside signed 32-bit range")

            tokens.append(str(node.val))
            visit(node.left)
            visit(node.right)

        visit(root)
        return self.SEP.join(tokens)

    def deserialize(self, data: str) -> TreeNode | None:
        if data == "":
            raise ValueError("serialization cannot be empty")

        tokens = iter(data.split(self.SEP))

        def build() -> TreeNode | None:
            try:
                token = next(tokens)
            except StopIteration:
                raise ValueError("serialization is truncated") from None

            if token == self.NULL:
                return None

            try:
                value = int(token)
            except ValueError:
                raise ValueError(f"invalid integer token: {token}") from None

            if value < MIN_INT32 or value > MAX_INT32:
                raise ValueError("node value is outside signed 32-bit range")

            node = TreeNode(value)
            node.left = build()
            node.right = build()
            return node

        root = build()

        try:
            extra = next(tokens)
        except StopIteration:
            return root

        raise ValueError(f"trailing token: {extra}")

Membina senarai token mengelakkan penyambungan rentetan berulang kali semasa penyirian. Penyahsiri berkongsi satu lelaran (iterator) antara panggilan rekursif, jadi anak tidak bermula semula dari awal. Memeriksa token yang tinggal selepas punca selesai menghalang input awalan sah seperti 1,#,#,9,#,# daripada diterima.

Langkah empat: buktikan bahawa penyahsiran menyongsangkan penyirian.

Gunakan aruhan berstruktur pada pokok T.

• Kes asas: jika T kosong, penyirian mengeluarkan #. Penyahsiri membaca #, mengembalikan None, dan

menggunakan tepat satu token subpokok tersebut.

• Langkah aruhan: andaikan dakwaan ini benar bagi subpokok kiri dan kanan. Penyirian mengeluarkan

nilai punca, diikuti dengan pengekodan kiri yang lengkap, kemudian pengekodan kanan yang lengkap. Penyahsiri mencipta punca yang sama, panggilan rekursif pertama menggunakan tepat pengekodan kiri mengikut hipotesis, dan yang kedua menggunakan tepat pengekodan kanan. Ia membina semula bentuk dan nilai yang sama serta berhenti serta-merta selepas T.

Oleh itu deserialize(serialize(T)) adalah sama dari segi struktur dengan T, dan setiap panggilan meninggalkan lelaran pada subpokok seterusnya yang belum dibaca. Pemeriksaan akhir token berlebihan mengesahkan bahawa punca menggunakan keseluruhan input.

Langkah lima: kira kos tanpa menyembunyikan output atau tindanan.

Kedua-dua operasi melawat setiap nod sebenar dan penuding null sekali, jadi masa ialah O(n). Output yang disiri dan input yang ditokenkan adalah O(n). Pokok yang dibina semula itu sendiri juga O(n). Penggunaan tindanan panggilan rekursif ialah O(h), dengan h ialah ketinggian pokok: O(log n) untuk pokok seimbang dan O(n) untuk pokok yang condong sepenuhnya.

Kod rekursif ialah jawapan temuduga yang baik apabila ketinggian adalah terhad dan kejelasan diutamakan. Ia tidak selamat untuk rantaian kawalan penyerang yang lebih panjang daripada had rekursi masa larian. Dalam kes itu, gunakan tindanan eksplisit atau baris gilir level-order dan kuat kuasakan had maksimum nod, token, bait, dan kedalaman.

Langkah enam: bandingkan DFS preorder dengan BFS level-order.

Kedua-duanya boleh diterbalikkan dalam masa dan ruang output O(n) jika mengekalkan maklumat null.

BFS lebih diutamakan apabila kedalaman rekursi merupakan risiko serta-merta atau sistem sekeliling sudah pun menggunakan perwakilan level-order. Preorder lebih diutamakan untuk temuduga asas kerana tatabahasa dan pembuktiannya lebih padat.

Langkah tujuh: sahkan perjalanan pergi balik (round trip) dan input tidak sah.

Ujian round-trip perlu merangkumi:

Tolak juga "", 1,#, x,#,#, 2147483648,#,#, dan 1,#,#,2,#,#. Bagi pokok yang dijana, bandingkan pokok asal dan pokok yang dinyahsiri secara rekursif serta buat penegasan serialize(deserialize(serialize(root))) == serialize(root). Ujian pokok condong harus dijalankan berhampiran sempadan ketinggian yang diterima supaya andaian tindanan dapat dilihat dengan jelas dan bukannya secara kebetulan.

Contoh Jawapan Berkualiti Tinggi

“Mula-mula saya akan mengesahkan bahawa ini ialah pokok perduaan sembarangan, nilainya ialah integer bertanda 32-bit, dan format itu hanya perlu dibaca oleh penyahsiri kita. Oleh kerana nilai pendua dibenarkan, saya perlu mengekodkan struktur secara eksplisit.

Saya akan menelusuri secara preorder. Untuk nod sebenar saya mengeluarkan nilainya, kemudian subpokok kiri dan kanannya; untuk anak yang tiada saya mengeluarkan #. Ini membezakan, contohnya, anak kiri daripada anak kanan walaupun nilai preorder adalah sama. Semasa penyahsiran, satu lelaran token yang dikongsi mencerminkan tatabahasa yang sama: # mengembalikan None; jika tidak, saya membina nod dan secara rekursif membina kiri kemudian kanan.

Ketepatan terbukti melalui aruhan berstruktur. Pokok kosong ialah satu #. Bagi punca sebenar, dengan mengandaikan setiap panggilan rekursif membina semula dan menggunakan tepat satu subpokok anak, kedua-dua panggilan menggunakan bahagian kiri dan kanan yang disiri mengikut urutan dan membina semula punca asal. Saya akan menolak penamatan pramatang, nilai tidak sah atau di luar julat, dan token berlebihan di belakang.

Setiap nod sebenar dan penuding null diproses sekali, jadi kedua-dua operasi adalah O(n). Teks dan token menggunakan ruang O(n), manakala rekursi menggunakan tindanan O(h). Jika ketinggian pokok boleh dimanipulasi secara berniat jahat, saya akan beralih kepada tindanan eksplisit atau BFS dan menetapkan had saiz serta kedalaman. Saya akan menguji kes kosong, nod tunggal, anak kiri sahaja berbanding anak kanan sahaja, pendua, nilai negatif, sempadan integer, rentetan tidak sah, dan round trip rawak.”

Kesilapan Biasa

• Menyirikan nilai nod sahaja → bentuk berbeza boleh menghasilkan traversal yang sama → **keluarkan

penanda null atau sempadan struktur eksplisit yang lain.**

• Menggunakan pembatas yang boleh muncul di dalam nilai → sempadan token menjadi samar-samar → **lepaskan (escape)

nilai, tambah panjang, atau pilih pembatas di luar tatabahasa nilai.**

• Mencipta lelaran (iterator) baharu dalam setiap panggilan rekursif → setiap anak membaca semula token pertama →

kongsi satu lelaran atau indeks yang bergerak ke hadapan.

• Menyahsiri punca dan mengabaikan baki teks → awalan yang sah menyembunyikan data rosak di belakang →

wajibkan penggunaan input secara lengkap.

• Membiarkan token yang hilang muncul sebagai pengecualian yang tidak berkaitan → data terpotong sukar didiagnosis →

tukarkan kehabisan pramatang kepada ralat penghuraian yang jelas.

• Mendakwa ruang tambahan sentiasa O(log n) → pokok condong mempunyai ketinggian n, dan penokenan

juga menggunakan ruang linear → asingkan kos output, penyimpanan token, pokok, dan tindanan panggilan.

• Menyatakan nilai preorder mencukupi untuk BST tanpa mentakrifkan pendua → kunci yang sama boleh menjadikan

pembinaan semula samar-samar → nyatakan peraturan susunan dan pendua sebelum membuang penanda.

• Menggunakan kod rekursif untuk kedalaman yang tidak dipercayai tanpa had → rantaian panjang boleh menghabiskan tindanan →

gunakan tindanan eksplisit dan had sumber.

• Membandingkan identiti objek selepas round trip → pembinaan semula menghasilkan nod baharu → **bandingkan

nilai dan struktur.**

• Hanya menguji contoh seimbang → kesamaran kiri/kanan dan risiko tindanan kekal tersembunyi → **sertakan

kes kosong, satu sisi, pendua, ekstrem, tidak sah, dan condong.**

Soalan Susulan dan Maklum Balas

Susulan 1: Bolehkah pokok carian perduaan (BST) meniadakan penanda null?

Selalunya boleh. Dengan tak varian BST yang ketat dan kunci unik, preorder boleh dibina semula dengan membawa sempadan bawah dan atas: nilai di dalam julat semasa tergolong dalam subpokok itu, dan nilai pertama di luarnya tergolong dalam leluhur. Jika pendua dibenarkan, kontrak mesti menyatakan sama ada nilai sama diletakkan di kiri, kanan, atau dikira di dalam nod. Tanpa dasar itu, format padat menjadi samar-samar. Masalah asas pokok sembarangan tidak boleh menggunakan pengoptimuman ini.

Susulan 2: Bagaimanakah anda menyokong nilai rentetan sembarangan?

Koma dan # mungkin wujud di dalam rentetan, jadi pemisahan pembatas tidak lagi menghadkan dirinya sendiri (self-delimiting). Satu pilihan ialah awalan panjang seperti 5:hello, diikuti dengan tag nod/null eksplisit. Pilihan lain ialah pustaka penyirian standard dengan skema. Pelepasan (escaping) boleh berfungsi, tetapi penyahsiri mesti membezakan pemisah yang dilepaskan daripada pemisah struktur dan mengendalikan jujukan pelepasan yang tidak sah. Awalan panjang menjadikan peraturan penggunaan lebih mudah dibuktikan.

Susulan 3: Apakah yang berubah untuk pokok dengan berjuta-juta nod atau kedalaman ekstrem?

Elakkan panggilan rekursif dan elakkan memecahkan keseluruhan input jika memori puncak penting. Strimkan token melalui penghurai berlelaran dengan tindanan eksplisit bagi slot anak, dan strimkan output kepada penulis dan bukannya mengumpul semua token terlebih dahulu. Kuat kuasakan had maksimum bait, token, nod, panjang integer, dan kedalaman sebelum memperuntukkan keadaan tanpa had. Masa kekal O(n), tetapi memori mengikut tindanan aktif atau baris gilir berserta dasar penimbal output.

Susulan 4: Bagaimanakah anda mengversikan format ini dalam sistem pengeluaran?

Tambah pengecam format dan versi di luar muatan (payload) pokok, tentukan lebar integer dan pengekodan teks, serta tentukan sama ada medan atau versi yang tidak diketahui akan gagal ditutup (fail closed). Sertakan semakan integriti apabila kerosakan data mesti dikesan, tetapi jangan anggap checksum sebagai pengesahan. Pelancaran memerlukan keserasian baca-lama/tulis-baharu dan lekapan (fixtures) bagi setiap versi yang disokong. Bagi perkhidmatan rentas bahasa, format berasaskan skema yang diselenggara biasanya lebih selamat daripada memperluaskan codec temuduga.

Susulan 5: Bolehkah penyirian level-order memangkas null di bahagian belakang dengan selamat?

Boleh, jika penyahsiri mentakrifkan kedudukan yang ditinggalkan selepas nod sebenar terakhir sebagai null dan penyiri hanya memangkas rentetan penanda null yang terakhir. Ia tidak boleh membuang null dalaman kerana tindakan itu mengubah penjajaran anak bagi nod terkemudian. Kontrak round-trip dan peraturan input tidak sah perlu diuji selepas pemangkasan; “kelihatan seperti tatasusunan yang lebih pendek” bukanlah bukti kesetaraan.