題目與適用情境
替任意二元樹實作兩個函式：
serialize(root)：將樹轉成字串。deserialize(data)：還原出值與結構都相同的樹。
假設節點值為 32 位元有號整數，樹可以為空，序列化字串只需要與本題的解碼器互通。遞迴面試實作還假設 樹高不超過語言的呼叫堆疊限制。下方解碼器會拒絕格式錯誤的文字，不會在只解析出部分樹時直接回傳。
對這棵樹：
1
/ \
2 3
/ \
4 5採用的格式是：
1,2,#,#,3,4,#,#,5,#,#每個整數記錄一個節點，# 記錄一個缺少的子節點，逗號分隔 token，前序走訪順序決定 token 的消耗方式。 2026 年更新的公開面試資料仍用前序與層序方案講解這題；interviewing.io 的面試回放也展示 Meta 工程師 參與的模擬面試中出現樹序列化題。這足以支持它是目前具代表性的 coding 練習，但不能延伸成所有公司都會問。
面試官考察重點
第一個訊號是候選人能否在選擇走訪順序前，先定義「可逆」。只保存前序節點值並不夠。根節點為 1、 左子節點為 2 的樹，與根節點為 1、右子節點為 2 的樹，都會產生 [1, 2]。加入空節點後才會不同：
左子節點：1,2,#,#,#
右子節點：1,#,2,#,#第二個訊號是能否把編碼器與解碼器設計成逆操作。前序解碼先讀一個 token：# 直接完成一棵空子樹； 整數則建立節點，緊接著的完整子樹屬於左子節點，再下一棵完整子樹屬於右子節點。格式不必另外保存子樹長度， 遞迴結構本身就給出邊界。
第三個訊號是有沒有真正的正確性說明。含 n 個節點的二元樹有 n + 1 個空子節點指標，所以編碼剛好 包含 2n + 1 個 token。更重要的不變量是：一次解碼呼叫必須剛好消耗一棵子樹的 token，並讓 iterator 停在下一棵子樹的開頭。這項性質可以用結構歸納證明。
最後還要看工程邊界：格式錯誤、負數與重複值、遞迴深度、輸出大小，以及何時該改用 BFS 或正式序列化協定。
回答前需要釐清的問題
- 這是任意二元樹，還是二元搜尋樹？ 任意樹需要結構標記；BST 在重複值策略明確時，可只用前序與邊界還原。
- 字串是否必須遵循現有傳輸格式？ 本題允許私有格式。跨服務保存還需要版本、相容規則與正式 codec。
- 節點值會不會包含分隔符號或哨兵？ 本題只有整數，逗號與
#不會衝突；一般字串需要跳脫或長度前綴。 - 樹可以為空嗎？ 可以，編碼為
#。 - 樹會不會非常深，或由不可信輸入建立？ 遞迴答案假設樹高受限；極深或對抗輸入應使用明確堆疊與資源限制。
deserialize是否只接收serialize的可信輸出？ 程式仍嚴格拒絕空字串、非法整數、截斷樹與尾隨 token。- 目標是可讀性還是最少位元組？ 前序文字方便說明與測試；精簡二進位協定會用不同的標籤與整數編碼。
30 秒回答框架
「我用前序走訪，並替每個缺少的子節點輸出 #。讀到整數就建立節點，再遞迴解碼左右子樹；讀到 # 就回傳空節點。空標記不能省，因為只保存節點值無法區分左子節點與右子節點。編碼與解碼的結構完全鏡像， 用結構歸納可以證明每次解碼剛好消耗一棵子樹。兩個操作都是 O(n) 時間，輸出為 O(n)，樹高為 h 時呼叫堆疊為 O(h)。我也會拒絕截斷或尾隨輸入；若深度無界，就改用迭代 BFS 或明確堆疊。」
分步深入解答
第一步：用反例淘汰「只保存節點值」。
單獨的前序、中序或後序節點值都不能唯一決定任意二元樹。允許重複值時，即使組合前序與中序也可能產生歧義。 格式必須同時保存值與結構；對面試字串而言，替每個空子節點寫一個哨兵是最直接的結構訊號。
第二步：選擇可以由左到右解碼的語法。
格式可以遞迴描述為：
tree := "#"
| integer "," tree "," tree實際程式會先依逗號拆成 token，所以每次遞迴先消耗一個 token；如果是整數，再消耗後續兩棵子樹。有號 整數文字不包含 , 或 #。空樹是 #，值為 7 的葉節點是 7,#,#。
這個語法也能導出一個檢查不變量。含 n 個真實節點的二元樹有 n + 1 個空子節點指標，因此序列化會 輸出 n 個數值 token 與 n + 1 個空 token，總數是 2n + 1。但 token 數為奇數不代表輸入一定 合法，解析時仍要檢查每個位置。
第三步：實作互相鏡像的遞迴操作。
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}")序列化先收集 token，避免在遞迴中反覆串接長字串。所有遞迴解碼呼叫共享同一個 iterator，子樹不會每次從 開頭重讀。根節點完成後再檢查剩餘 token，可以拒絕 1,#,#,9,#,# 這種「前綴合法、後面仍有垃圾」的輸入。
第四步：證明解碼確實是編碼的逆操作。
對樹 T 做結構歸納：
- 基礎情況：
T為空，編碼輸出#。解碼器讀到#後回傳None，並剛好消耗這棵空子樹的一個 token。 - 歸納情況：假設左右子樹都滿足結論。編碼先輸出根值，再依序輸出完整的左、右子樹。解碼器建立相同根節點；
第一次遞迴依歸納假設剛好消耗左子樹，第二次剛好消耗右子樹，因此值與結構完全還原，並停在 T 之後。
所以 deserialize(serialize(T)) 與 T 結構相同，而且每次呼叫都會讓 iterator 留在下一段未讀子樹。 最後的尾隨 token 檢查進一步確認根節點消耗了全部輸入。
第五步：計算成本，不隱藏輸出與呼叫堆疊。
兩個操作都會拜訪每個真實節點與空指標一次，因此時間是 O(n)。序列化結果與拆開後的 token 都是 O(n)；新建的樹本身也是 O(n)。遞迴呼叫堆疊為 O(h)，其中 h 是樹高：平衡樹為 O(log n)， 完全偏斜的樹為 O(n)。
樹高受限且重視程式清楚時，遞迴版很適合面試。若輸入可由攻擊者提供，一條超過執行環境遞迴限制的長鏈就會 耗盡呼叫堆疊。此時應使用明確堆疊或層序 queue，並限制最大節點數、token 數、位元組數與深度。
第六步：比較前序 DFS 與層序 BFS。
只要保留空節點資訊，兩者都能以 O(n) 時間與輸出空間完成可逆編碼。
| 格式 | 主要優點 | 主要代價 | |---|---|---| | 帶空標記的前序 DFS | 編碼與解碼具有相同遞迴結構 | 遞迴版需要 O(h) 呼叫堆疊 | | 帶空標記的層序 BFS | 迭代實作，接近常見陣列樹表示 | queue 可能保存 O(w) 個節點，稀疏樹文字較長 | | 只保存值 | 字串短 | 遺失任意二元樹結構 | | 帶版本的標準二進位格式 | 可互通，並能精簡保存型別欄位 | 協定複雜度超出本題範圍 |
遞迴深度是首要風險，或周邊系統已經使用層序格式時，BFS 較合適。基礎面試中，前序方案的語法與證明更短。
第七步：驗證往返結果與格式錯誤。
往返測試至少包括：
| 案例 | 預期編碼 | |---|---| | 空樹 | # | | 單一節點 7 | 7,#,# | | 根 1，左子節點 2 | 1,2,#,#,# | | 根 1，右子節點 2 | 1,#,2,#,# | | 兩個負數重複子節點 | 結構與兩個重複值都保留 | | 32 位元有號整數兩端 | 上下界都能解析並往返 |
也要拒絕 ""、1,#、x,#,#、2147483648,#,# 與 1,#,#,2,#,#。對隨機產生的樹，遞迴 比較原樹與還原樹，並斷言 serialize(deserialize(serialize(root))) == serialize(root)。偏斜樹測試應接近允許的高度邊界， 讓呼叫堆疊假設成為明確契約。
高品質示範回答
「我先確認這是任意二元樹，節點值是 32 位元有號整數，而且格式只需由自己的解碼器讀取。因為允許重複值， 結構必須明確編碼。
我採用前序走訪。真實節點先輸出值，再輸出左右子樹；缺少的子節點輸出 #。如此即使前序節點值相同， 也能區分左子節點與右子節點。解碼時共享一個 token iterator，讀到 # 回傳空；否則建立節點，再依序 還原左右子樹。
正確性可用結構歸納。空樹對應一個 #；對真實根節點，若兩次遞迴都能還原並剛好消耗一棵子樹，它們就會 依編碼順序消耗左右部分並還原原本根節點。我也會拒絕輸入提早結束、非法或越界整數及尾隨 token。
每個真實節點與空指標只處理一次，因此兩個操作都是 O(n)。文字與 token 使用 O(n) 空間，遞迴堆疊 為 O(h)。若樹高可能是對抗性的，我會改用明確堆疊或 BFS，並設定大小與深度限制。測試涵蓋空樹、單一 節點、只有左子節點和只有右子節點、重複值、負數、整數邊界、非法字串及隨機往返。」
常見錯誤
- 只序列化節點值 → 不同結構可能得到相同走訪 → 輸出空標記或其他明確的結構邊界。
- 分隔符號可能出現在節點值中 → token 邊界產生歧義 → 跳脫節點值、增加長度，或選擇值語法外的分隔符號。
- 每次遞迴都建立新 iterator → 每棵子樹都從第一個 token 重讀 → 共享一個持續前進的 iterator 或索引。
- 解出根節點後忽略剩餘文字 → 合法前綴會掩蓋後續損壞資料 → 要求完整消耗輸入。
- 讓缺少 token 丟出無關例外 → 截斷資料難以定位 → 把提早耗盡轉成明確解析錯誤。
- 宣稱輔助空間永遠為
O(log n)→ 偏斜樹高度為n，拆開 token 也占線性空間 → 分別說明輸出、token、樹與呼叫堆疊。 - 未定義重複值便宣稱 BST 前序不需要空標記 → 相同鍵可能產生歧義 → 先定義排序與重複值策略。
- 對不可信深度直接使用遞迴 → 長鏈會耗盡呼叫堆疊 → 改用明確堆疊並設定資源上限。
- 往返後比較物件 identity → 重建過程會建立新節點 → 比較節點值與結構。
- 只測試平衡樹範例 → 左右歧義與堆疊風險不會暴露 → 加入空樹、單側樹、重複值、極值、非法與偏斜案例。
追問與應對
追問一：二元搜尋樹可以省略空標記嗎？
通常可以。若 BST 使用嚴格大小關係且鍵唯一，可在解碼前序序列時帶著上下界：位於目前範圍內的值屬於 目前子樹，第一個超出範圍的值留給祖先。若允許重複值，契約必須說明相等值放左邊、右邊，或在節點內計數； 沒有這項規則，精簡格式仍有歧義。任意二元樹的基礎題不能使用這項最佳化。
追問二：如果節點值是任意字串，如何處理？
逗號與 # 都可能出現在字串中，簡單 split 無法再確認邊界。可使用 5:hello 這類長度前綴，並另外保留 節點與空節點標籤；也可以使用帶 schema 的標準序列化函式庫。跳脫方案也可行，但解碼器要區分被跳脫的 分隔符號與結構分隔符號，並處理非法跳脫。長度前綴的消耗規則通常更容易證明。
追問三：樹有數百萬節點或極端深度時怎麼辦？
避免遞迴呼叫；若尖峰記憶體也重要，不要一次 split 完整輸入。讓迭代解析器以串流方式讀 token，用明確 堆疊記錄尚未填入的子節點位置；編碼端寫入 stream，而非先收集全部 token。配置無界狀態前限制最大位元組、 token、節點、整數長度與深度。時間仍為 O(n)，記憶體取決於活動堆疊或 queue 及輸出緩衝策略。
追問四：正式系統如何替格式加版本？
在樹 payload 外增加格式識別與版本，明確指定整數寬度和文字編碼，並規定未知欄位與未知版本要拒絕或忽略。 需要偵測損壞時可加入完整性檢查，但 checksum 不能當成身分驗證。發布流程要支援「讀舊寫新」，並替每個 受支援版本保存固定測試樣本。跨語言服務通常應採用維護中的 schema 格式，而非繼續擴充這段面試 codec。
追問五：層序序列化可以安全刪除尾端空標記嗎？
可以，前提是解碼器明確把最後一個真實節點之後省略的位置都視為空，而且編碼器只刪除尾端連續的空標記。 內部空位不能刪除，否則後續節點的子節點對齊會改變。刪除後仍要重新驗證往返契約與格式錯誤規則；字串看起來 較短並不能證明兩種格式等價。