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

# 536. Construct Binary Tree from String

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

把 `4(2(3)(1))(6(5))` 這種括號字串還原成一棵二元樹。做這題之前可以先完成 [606. Construct String from Binary Tree](/interview/coding/606-construct-string-from-binary-tree)。

## 思路

[606](/interview/coding/606-construct-string-from-binary-tree) 是把樹寫成字串，用的是前序；這題是反過來，要從字串把結構剖析出來。子樹的結構長這樣：

```text
子樹 = 根節點（左子樹）（右子樹）
```

從這個結構來看，我們**優先知道的是根節點** —— 它就在最前面，前面沒有任何括號擋著。所以這題也是前序的形狀：先把根拿出來，再處理兩棵子樹。

而括號裡面裝的東西，本身又是同樣的結構：

```text
（左子樹）（右子樹）

    == （左子樹的根（左左）（左右)）（右子樹的根（右左）（右右)）
```

所以只要**把子樹外面那層括號剝掉**，剩下的字串就可以套用同一個函式遞迴下去。

整題於是拆成兩件事：怎麼取根節點的值、怎麼找出兩對括號的範圍。

### 取得根節點的值

根節點的值不會被括號影響，只要從當前位置往後掃到「不是數字也不是負號」為止就好。負號不用特別處理 —— Python 的 `int()` 直接吃得下 `"-4"`。

```python
end = begin
if begin == len(s):
    return None
while end < len(s) and (s[end].isdigit() or s[end] == '-'):
    end += 1
root = TreeNode(int(s[begin:end]))
```

`if begin == len(s): return None` 同時處理了「空字串」和「這棵子樹是空的」—— 也就是 606 留下的那個空 `()`，剝掉括號之後就是空字串。

### 找出括號的範圍

這裡不能只找下一個 `)`，因為括號會巢狀。要用**棧來配對**，跟 [20. Valid Parentheses](/interview/coding/20-valid-parentheses) 是同一招：遇到 `(` 推入、遇到 `)` 彈出，**棧空的那一刻就是這對括號的結尾**。

```python
begin = end
if end < len(s) and s[end] == '(':
    stack = []
    stack.append(s[end])
    end += 1
    while end < len(s) and stack:
        if s[end] == '(':
            stack.append(s[end])
        if s[end] == ')':
            stack.pop()
        end += 1
    root.left = traverse(s[begin+1:end-1], 0)
```

`s[begin+1:end-1]` 就是「剝掉最外層那對括號」—— 這正是遞迴能成立的關鍵。找右子樹是完全一樣的一段，只是把結果接到 `root.right`。

因為 606 的省略規則保證了「第一對括號一定是左子樹」，所以照順序處理就不會弄錯 —— 左子樹是空的時候，那對括號會是 `()`，剝掉之後遞迴回傳 `None`。

## 解題方向

### 切片版

```python
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def str2tree(self, s: str) -> Optional[TreeNode]:       
        def traverse(s, begin):
            end = begin
            if begin == len(s):
                return None
            while end < len(s) and (s[end].isdigit() or s[end] == '-'):
                end += 1
            root = TreeNode(int(s[begin:end]))
            begin = end
            if end < len(s) and s[end] == '(':
                stack = []
                stack.append(s[end])
                end += 1
                while end < len(s) and stack:
                    if s[end] == '(':
                        stack.append(s[end])
                    if s[end] == ')':
                        stack.pop()
                    end += 1
                root.left = traverse(s[begin+1:end-1], 0)
            begin = end
            if end < len(s) and s[end] == '(':
                stack = []
                stack.append(s[end])
                end += 1
                while end < len(s) and stack:
                    if s[end] == '(':
                        stack.append(s[end])
                    if s[end] == ')':
                        stack.pop()
                    end += 1
                root.right = traverse(s[begin+1:end-1], 0)
            return root
        return traverse(s, 0)
```

兩段找括號的邏輯一模一樣，只差最後接到 `left` 還是 `right`，抽成一個小函式會更短。留成兩段的好處是「先左後右」的順序一眼就看得到。

這一版有個瑕疵：`s[begin+1:end-1]` 每遞迴一層就複製一份新字串。斜樹上每一層都在複製近乎整個字串，記憶體會爆掉，時間也白花。

### 傳索引版

改法很機械：**不要切字串，改成把「這棵子樹的範圍」當成兩個索引傳下去。** 原本的 `len(s)` 換成上界 `stop`，原本的 `traverse(s[begin+1:end-1], 0)` 換成 `traverse(begin + 1, end - 1)`，其他一行都不用動。

```python
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def str2tree(self, s: str) -> Optional[TreeNode]:
        def traverse(begin, stop):
            if begin == stop:
                return None
            end = begin
            while end < stop and (s[end].isdigit() or s[end] == '-'):
                end += 1
            root = TreeNode(int(s[begin:end]))
            begin = end
            if end < stop and s[end] == '(':
                stack = []
                stack.append(s[end])
                end += 1
                while end < stop and stack:
                    if s[end] == '(':
                        stack.append(s[end])
                    if s[end] == ')':
                        stack.pop()
                    end += 1
                root.left = traverse(begin + 1, end - 1)
            begin = end
            if end < stop and s[end] == '(':
                stack = []
                stack.append(s[end])
                end += 1
                while end < stop and stack:
                    if s[end] == '(':
                        stack.append(s[end])
                    if s[end] == ')':
                        stack.pop()
                    end += 1
                root.right = traverse(begin + 1, end - 1)
            return root
        return traverse(0, len(s))
```

`begin == stop` 取代了原本的 `begin == len(s)`，一樣同時處理「空字串」和「空的 `()`」—— 剝掉括號之後 `begin` 和 `stop` 會相等。

`int(s[begin:end])` 那個切片留著沒關係，它的長度是數字的位數，跟子樹大小無關。

**但要說清楚：這一版省掉的是複製，不是重掃。** 找左子樹的括號範圍時，那個 `while` 已經把左子樹的字串整段走過一遍，遞迴進去之後又會再走一遍。所以時間量級跟切片版一樣是 $O(n \cdot h)$，只是不再產生一堆暫時字串。**真正的改善在空間。**

### 單一游標版

前兩版都有同一個累贅：**為了知道子樹的括號在哪結束，得先掃一遍**。但其實根本不用先知道 —— 讓遞迴自己走到那裡就好。

把索引改成一個**單向前進、所有層共用**的游標，規則只有三條：

1. 讀完數字，游標停在數字後面
2. 看到 `(`，**吃掉它**，遞迴下去
3. 遞迴回來時，游標剛好停在配對的 `)` 上，**吃掉它**

第 3 條是整個做法成立的關鍵：子函式讀到 `)` 就會回傳（那是它的終止條件），所以它回來的時候，游標必定停在自己那對括號的收尾上。**配對是遞迴自己完成的，不需要棧。**

```python
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def str2tree(self, s: str) -> Optional[TreeNode]:
        index = 0

        def traverse():
            nonlocal index
            if index == len(s) or s[index] == ')':
                return None

            begin = index
            while index < len(s) and (s[index].isdigit() or s[index] == '-'):
                index += 1
            root = TreeNode(int(s[begin:index]))

            if index < len(s) and s[index] == '(':
                index += 1                  # 吃掉 '('
                root.left = traverse()
                index += 1                  # 吃掉配對的 ')'
            if index < len(s) and s[index] == '(':
                index += 1
                root.right = traverse()
                index += 1
            return root

        return traverse()
```

終止條件多了 `s[index] == ')'` 這一項，它就是在處理空子樹 —— 也就是 [606](/interview/coding/606-construct-string-from-binary-tree) 留下的那個 `()`。進去之後立刻撞到 `)`，回傳 `None`，外層再把那個 `)` 吃掉。

拿 `4(2)(5)` 走一遍，看游標怎麼單向推進：

```text
動作                  index
讀到 4                  1
吃掉 ( 進左子樹          2
  讀到 2                3
吃掉 ) 離開左子樹        4
吃掉 ( 進右子樹          5
  讀到 5                6
吃掉 ) 離開右子樹        7
```

`index` 從 0 到 7 只往前走，沒有回頭過 —— 這就是 $O(n)$ 的來源。

**代價是遞迴不再是純函式**：它依賴並修改外層的 `index`，所以呼叫的順序有意義，`root.left` 那兩行和 `root.right` 那兩行絕對不能對調。前兩版把範圍當參數傳，反而沒有這個限制。

## 補充

**共用游標這個手法在別的地方也出現過**：[394. Decode String](/interview/coding/394-decode-string) 的遞迴版用的就是 `nonlocal index`，[297](/interview/coding/297-serialize-and-deserialize-binary-tree) 的前序反序列化則是用 `deque` 從左邊消耗。三題的心法是同一句：**不要複製資料，也不要回頭重掃，只推進位置。**

**只用一個棧也能做，不用遞迴**：掃字串時遇到數字就建節點掛到棧頂那個節點上（左邊沒滿掛左邊，否則掛右邊），遇到 `)` 就 `pop`。我沒有用這個角度寫過，但那是這題的迭代解。

**同一個題組**：

| 題目 | 方向 | 格式 |
|---|---|---|
| [606](/interview/coding/606-construct-string-from-binary-tree) | 樹 → 字串 | 括號 |
| 536 | 字串 → 樹 | 括號 |
| [297](/interview/coding/297-serialize-and-deserialize-binary-tree) | 兩邊都要 | **自己選**（哨兵最省事） |
| [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)。

## 複雜度

$n$ 是字串長度、`h` 是樹高（平衡時 $O(\log n)$、斜樹 $O(n)$）。

| 寫法 | 時間 | 空間 |
|---|---|---|
| 切片版 | $O(n \cdot h)$ | $O(n \cdot h)$ — 每層都留著一份子字串 |
| 傳索引版 | $O(n \cdot h)$ | $O(h)$ — 只有遞迴堆疊 |
| 單一游標 | $O(n)$ | $O(h)$ |

前兩版的 $O(n \cdot h)$ 都來自同一件事：**每一層都要掃一遍才能找到括號的配對位置，而那一遍的長度就是這棵子樹的字串長度。** 斜樹上 $h = n$，所以最壞是 $O(n^2)$。

傳索引沒有改變掃描次數，改變的是「有沒有真的把那段字串複製出來」—— 所以時間量級一樣，空間差很多。