--- title: "297. Serialize and Deserialize Binary Tree" url: "https://laigary.com/interview/coding/297-serialize-and-deserialize-binary-tree" type: "note" section: "coding" date: "2023-01-29" updated: "2026-07-29" tags: ["Design", "Tree", "Breadth-First Search", "Depth-First Search", "Classic"] --- # 297. Serialize and Deserialize Binary Tree [297\. Serialize and Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/) 把一棵二元樹編碼成字串，再從那個字串還原回一模一樣的樹。 ## 思路 這題掛 Hard，但它其實比 [606](/interview/coding/606-construct-string-from-binary-tree) 和 [536](/interview/coding/536-construct-binary-tree-from-string) 好寫 —— 因為**格式是你自己定的**。606/536 的括號格式是題目定死的，你只能照著解析；這題你可以挑一個最好還原的格式。 那就直接用那兩題的括號格式來解 297 行不行？可以，但沒必要 —— 那樣要寫括號配對，長得多。 ### 關鍵是「子樹的邊界要看得出來」 一個格式能不能還原，取決於**讀到哪裡代表一棵子樹結束了**。光把節點值照前序印出來是不夠的： ```text 1 1 / \ 2 2 前序都是 [1, 2] ← 分不出來 ``` 要補上邊界資訊，有兩條路： 1. **哨兵**：把空節點也寫出來（用 `#`）。這樣前序序列就唯一決定一棵樹了 —— 哨兵這個手法見 [Python 面試技巧](/interview/coding/python-tips-for-interview) 2. **括號**：明確標出每棵子樹從哪開始到哪結束 —— 那是 606/536 的做法 順帶一提，這也解釋了 [105. 前序+中序建樹](/interview/coding/105-construct-binary-tree-from-preorder-and-inorder-traversal) 為什麼需要**兩個**序列：它的序列裡沒有哨兵，所以要靠中序來切出左右子樹的範圍。**加哨兵和多給一個序列，是補同一個資訊的兩種方式。** ### 中序 + 哨兵不行 前序、後序、層序加上哨兵都能唯一還原，但**中序不行**： ```text 1 2 / \ 2 1 中序 + 哨兵都是 #,2,#,1,# ← 還是分不出來 ``` 原因是中序把根節點夾在中間，讀到根的時候左邊已經讀完了，但你不知道那一段有多深。前序和後序的根固定在一端（開頭或結尾），才能靠遞迴一路切下去。 ## 解題方向 三種格式都可以，共同點是**序列化和反序列化必須是同一套走訪順序的鏡像**。 ### 前序 + 哨兵 最直觀的一種：根先出現，所以反序列化時可以直接建根，再遞迴建左右。 ```python # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root): res = [] def traverse(root): if not root: res.append('#') return res.append(str(root.val)) traverse(root.left) traverse(root.right) traverse(root) return ','.join(res) def deserialize(self, data): if not data: return None nodes = deque(data.split(',')) def traverse(nodes): rootVal = nodes.popleft() if rootVal == '#': return None root = TreeNode(rootVal) root.left = traverse(nodes) root.right = traverse(nodes) return root return traverse(nodes) ``` 用 `deque` 而不是 list，是因為要從**前面**取值 —— `list.pop(0)` 是 $O(n)$，整體會退化。 反序列化不需要知道「這棵子樹佔幾個 token」，因為遞迴會自己把該吃的吃完 —— 建完左子樹之後，`nodes` 的最前面剛好就是右子樹的第一個 token。**這種「共用一個游標，誰用誰推進」的寫法，跟 [224 計算機](/interview/coding/224-basic-calculator) 用 `deque` 是同一個手法。** ### 後序 + 哨兵 後序的根在**最後**，所以要**從尾巴往前讀**，而且順序整個鏡像：先建右子樹再建左子樹。 ```python class Codec: def serialize(self, root): res = [] def traverse(root): if not root: res.append('#') return traverse(root.left) traverse(root.right) res.append(str(root.val)) traverse(root) return ','.join(res) def deserialize(self, data): if not data: return None nodes = data.split(',') def traverse(nodes): rootVal = nodes.pop() if rootVal == '#': return None root = TreeNode(rootVal) root.right = traverse(nodes) root.left = traverse(nodes) return root return traverse(nodes) ``` `root.right` 寫在 `root.left` 前面 —— 這一行寫反了就整棵樹左右顛倒。因為是從尾巴 pop，這裡用 list 就好，`list.pop()` 從尾端彈出是 $O(1)$。 ### 廣度優先 BFS 一層一層存，格式跟 LeetCode 顯示樹的方式最接近。 ```python class Codec: def serialize(self, root): res = [] q = deque([root]) while q: size = len(q) for i in range(size): node = q.popleft() if node: res.append(str(node.val)) q.append(node.left) q.append(node.right) else: res.append('#') return ','.join(res) def deserialize(self, data): if not data: return None nodes = deque(data.split(',')) rootVal = nodes.popleft() if rootVal == '#': return None root = TreeNode(int(rootVal)) q = deque([root]) while q: size = len(q) for i in range(size): node = q.popleft() leftVal = nodes.popleft() rightVal = nodes.popleft() if leftVal != '#': node.left = TreeNode(int(leftVal)) q.append(node.left) if rightVal != '#': node.right = TreeNode(int(rightVal)) q.append(node.right) return root ``` 配對規則是：**每個非空節點，在串流裡後面一定緊跟著它的兩個孩子**（空的話是 `#`）。序列化時 `#` 不再往下推孩子，所以反序列化也只對非空節點各取兩個 token，兩邊剛好對上。 分層的骨架跟 [102](/interview/coding/102-binary-tree-level-order-traversal) 一樣：先固定 `len(q)` 再跑。 ## 補充 **前序和後序版沒有把值轉回 `int`**（`TreeNode(rootVal)` 收到的是字串），只有 BFS 版寫了 `int(rootVal)`。因為 `serialize` 裡是 `str(root.val)`，字串進字串出，往返結果一致所以不影響判題。但三個版本統一成 `TreeNode(int(rootVal))` 比較不會踩到坑 —— 一旦有人拿還原後的樹去做數值比較（例如接著跑 [98](/interview/coding/98-validate-binary-search-tree)），字串的比較規則就完全不一樣了。 **[449. Serialize and Deserialize BST](/interview/coding/449-serialize-and-deserialize-bst) 可以更省**：因為是 BST，前序序列**不需要哨兵**也能唯一還原 —— 反序列化時靠值域範圍就知道該停在哪，跟 [98](/interview/coding/98-validate-binary-search-tree) 傳上下界是同一招。這就是「額外的結構資訊可以取代哨兵」。 **同一個題組**： | 題目 | 方向 | 格式 | |---|---|---| | 297 | 兩邊都要 | **自己選**（哨兵最省事） | | [606. Construct String from Binary Tree](/interview/coding/606-construct-string-from-binary-tree) | 樹 → 字串 | 括號（題目定死） | | [536. Construct Binary Tree from String](/interview/coding/536-construct-binary-tree-from-string) | 字串 → 樹 | 括號（題目定死） | | [449. Serialize and Deserialize BST](/interview/coding/449-serialize-and-deserialize-bst) | 兩邊都要 | 前序，**不用哨兵** | | [428. Serialize and Deserialize N-ary Tree](/interview/coding/428-serialize-and-deserialize-n-ary-tree) | 兩邊都要 | 要多存「有幾個小孩」 | 428 的重點在於：二元樹的孩子數固定是 2，所以哨兵就夠了；N 元樹的孩子數不固定，**必須額外記錄數量或用括號劃界**。 ## 複雜度 三種格式都是： - 時間 $O(n)$ — 序列化和反序列化各走過每個節點一次 - 空間 $O(n)$ — 輸出的字串本身就是 $O(n)$；遞迴堆疊或佇列另外是 $O(h)$ / $O(w)$ 其中 $n$ 是節點數、`h` 是樹高、`w` 是最寬那層的節點數。 **哨兵讓字串變長但沒有改變量級**：一棵有 $n$ 個節點的二元樹恰好有 $n + 1$ 個空位，所以 token 總數是 $2n + 1$，還是 $O(n)$。