---
title: "606. Construct String from Binary Tree"
url: "https://laigary.com/interview/coding/606-construct-string-from-binary-tree"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-28"
tags: ["String", "Tree", "Depth-First Search"]
---

# 606. Construct String from Binary Tree

[606\. Construct String from Binary Tree](https://leetcode.com/problems/construct-string-from-binary-tree/)

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

## 思路

這題是 [536](/interview/coding/536-construct-binary-tree-from-string) 的反方向，兩題合起來就是一組序列化 / 反序列化。

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

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

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

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

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

```text
    2                 2
   /                   \
  3                     3

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

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

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

四種情況：

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

## 解題方向

```python
# 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](/interview/coding/536-construct-binary-tree-from-string) 好解析。** 讀字串時，`(` 後面若立刻是 `)`，就代表左邊是空的；否則第一對括號一定是左子樹。省略規則設計得剛好保留了足夠的資訊，不多也不少。

**跟 [297](/interview/coding/297-serialize-and-deserialize-binary-tree) 的哨兵法對照**：兩者都在解決同一個問題 —— 讓「子樹的邊界」在字串裡看得出來。

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

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

**同一個題組**：[297](/interview/coding/297-serialize-and-deserialize-binary-tree)、[536](/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)。整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

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

其中 $n$ 是節點數、`h` 是樹高。這個「每層重新拼接」的退化跟 [94 中序遍歷](/interview/coding/94-binary-tree-inorder-traversal) 的 `extend` 版是同一回事。