297. Serialize and Deserialize Binary Tree

──────────────────────────────────────────────────────────────────────

把一棵二元樹編碼成字串，再從那個字串還原回一模一樣的樹。

思路

這題掛 Hard，但它其實比 606 和 536 好寫 —— 因為格式是你自己定的。606/536 的括號格式是題目定死的，你只能照著解析；這題你可以挑一個最好還原的格式。

那就直接用那兩題的括號格式來解 297 行不行？可以，但沒必要 —— 那樣要寫括號配對，長得多。

關鍵是「子樹的邊界要看得出來」

一個格式能不能還原，取決於讀到哪裡代表一棵子樹結束了。光把節點值照前序印出來是不夠的：

    1              1
   /                \
  2                  2

前序都是 [1, 2]        ← 分不出來

要補上邊界資訊，有兩條路：

哨兵：把空節點也寫出來（用 #）。這樣前序序列就唯一決定一棵樹了 —— 哨兵這個手法見 Python 面試技巧
括號：明確標出每棵子樹從哪開始到哪結束 —— 那是 606/536 的做法

順帶一提，這也解釋了 105. 前序+中序建樹為什麼需要兩個序列：它的序列裡沒有哨兵，所以要靠中序來切出左右子樹的範圍。加哨兵和多給一個序列，是補同一個資訊的兩種方式。

中序 + 哨兵不行

前序、後序、層序加上哨兵都能唯一還原，但中序不行：

    1              2
   /                \
  2                  1

中序 + 哨兵都是 #,2,#,1,#      ← 還是分不出來

原因是中序把根節點夾在中間，讀到根的時候左邊已經讀完了，但你不知道那一段有多深。前序和後序的根固定在一端（開頭或結尾），才能靠遞迴一路切下去。

解題方向

三種格式都可以，共同點是序列化和反序列化必須是同一套走訪順序的鏡像。

前序 + 哨兵

最直觀的一種：根先出現，所以反序列化時可以直接建根，再遞迴建左右。

# 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 計算機用 deque 是同一個手法。

後序 + 哨兵

後序的根在最後，所以要從尾巴往前讀，而且順序整個鏡像：先建右子樹再建左子樹。

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 顯示樹的方式最接近。

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 一樣：先固定 len(q) 再跑。

補充

前序和後序版沒有把值轉回 int（TreeNode(rootVal) 收到的是字串），只有 BFS 版寫了 int(rootVal)。因為 serialize 裡是 str(root.val)，字串進字串出，往返結果一致所以不影響判題。但三個版本統一成 TreeNode(int(rootVal)) 比較不會踩到坑 —— 一旦有人拿還原後的樹去做數值比較（例如接著跑 98），字串的比較規則就完全不一樣了。

449. Serialize and Deserialize BST 可以更省：因為是 BST，前序序列不需要哨兵也能唯一還原 —— 反序列化時靠值域範圍就知道該停在哪，跟 98 傳上下界是同一招。這就是「額外的結構資訊可以取代哨兵」。

同一個題組：

題目	方向	格式
297	兩邊都要	自己選（哨兵最省事）
606. Construct String from Binary Tree	樹 → 字串	括號（題目定死）
536. Construct Binary Tree from String	字串 → 樹	括號（題目定死）
449. Serialize and Deserialize BST	兩邊都要	前序，不用哨兵
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 總數是 $2 n + 1$ ，還是 $O (n)$ 。