606. Construct String from Binary Tree

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

把一棵二元樹寫成 根(左子樹)(右子樹) 這種括號字串，而且要省掉所有不影響還原的空括號。

思路

這題是 536 的反方向，兩題合起來就是一組序列化 / 反序列化。

基本形狀是前序：先寫自己，再把左右子樹各自包在一對括號裡。難的不是遞迴，是什麼時候可以省略括號。

括號存在的唯一理由是「分辨左右」

如果不省略，一個葉節點會寫成 4()()，那兩對空括號沒有帶任何資訊 —— 讀的人看到 4 後面沒東西，自然知道它沒有小孩。所以葉節點直接寫 4。

同樣的道理，只有左子樹時右邊那對可以省：2(3) 讀起來沒有歧義，括號裡的一定是左子樹。

但只有右子樹時就不行了：

    2                 2
   /                   \
  3                     3

如果都寫成 2(3)  ← 分不出來

所以右子樹存在而左子樹不存在時，必須留一個空的 () 佔位，寫成 2()(3)。

空括號不是裝飾，它是在說「這裡本來有個位置，是空的」。 這就是整題的全部。

四種情況：

左	右	輸出
無	無	`4`
有	無	`4(左)`
無	有	`4()(右)` ← 空括號不能省
有	有	`4(左)(右)`

解題方向

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:

        def traverse(root):
            if not root:
                return ''
            left = traverse(root.left)
            right = traverse(root.right)
            if len(left) == 0 and len(right) == 0:
                return str(root.val)
            elif len(left) == 0:
                return str(root.val) + '()' + '(' + right  +')'
            elif len(right) == 0:
                return str(root.val) + '(' + left  +')'
            return str(root.val) + '(' + left + ')' + '(' + right  +')'
        return traverse(root)

用 len(left) == 0 判斷「沒有左子樹」是安全的：traverse 只有在節點是 None 時才回傳空字串，任何真實節點至少會回傳 str(root.val)，不可能是空的。

四個分支的順序也有講究 —— 先擋掉兩個都沒有的情況，剩下的三種才好判斷。如果先寫 len(left) == 0 那一支，葉節點就會被誤判成「只有右子樹」。

補充

這個省略規則就是為什麼 536 好解析。 讀字串時，( 後面若立刻是 )，就代表左邊是空的；否則第一對括號一定是左子樹。省略規則設計得剛好保留了足夠的資訊，不多也不少。

跟 297 的哨兵法對照：兩者都在解決同一個問題 —— 讓「子樹的邊界」在字串裡看得出來。

	邊界怎麼標	空節點	解析難度
297（哨兵）	靠 `#` 的位置	每一個都要寫	遞迴一路吃，很短
606 / 536（括號）	靠 `(` `)` 配對	只寫必要的那些	要做括號配對

括號版的字串比較短也比較好讀，代價是解析要寫配對邏輯。297 讓你自己選格式，所以那題選哨兵。

同一個題組：297、536、449. Serialize and Deserialize BST、428. Serialize and Deserialize N-ary Tree。整理見 Tree 遍歷模板。

複雜度

時間 $O (n^{2})$ 最壞 — 每一層都在把子樹回傳的字串重新串接一次，斜樹上會退化；改成把片段 append 進一個共用的 list、最後 ''.join() 就是嚴格 $O (n)$
空間 $O (n)$ — 輸出字串本身，加上 $O (h)$ 的遞迴堆疊

其中 $n$ 是節點數、h 是樹高。這個「每層重新拼接」的退化跟 94 中序遍歷的 extend 版是同一回事。