536. Construct Binary Tree from String
536. Construct Binary Tree from String
把 4(2(3)(1))(6(5)) 這種括號字串還原成一棵二元樹。做這題之前可以先完成 606. Construct String from Binary Tree。
思路
606 是把樹寫成字串，用的是前序；這題是反過來，要從字串把結構剖析出來。子樹的結構長這樣：
子樹 = 根節點（左子樹）（右子樹）
從這個結構來看，我們優先知道的是根節點 —— 它就在最前面，前面沒有任何括號擋著。所以這題也是前序的形狀：先把根拿出來，再處理兩棵子樹。
而括號裡面裝的東西，本身又是同樣的結構：
（左子樹）（右子樹）
== （左子樹的根（左左）（左右)）（右子樹的根（右左）（右右)）
所以只要把子樹外面那層括號剝掉，剩下的字串就可以套用同一個函式遞迴下去。
整題於是拆成兩件事：怎麼取根節點的值、怎麼找出兩對括號的範圍。
取得根節點的值
根節點的值不會被括號影響，只要從當前位置往後掃到「不是數字也不是負號」為止就好。負號不用特別處理 —— Python 的 int() 直接吃得下 "-4"。
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 是同一招：遇到 ( 推入、遇到 ) 彈出，棧空的那一刻就是這對括號的結尾。
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。
解題方向
切片版
# 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)，其他一行都不用動。
# 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 已經把左子樹的字串整段走過一遍，遞迴進去之後又會再走一遍。所以時間量級跟切片版一樣是 ，只是不再產生一堆暫時字串。真正的改善在空間。
單一游標版
前兩版都有同一個累贅：為了知道子樹的括號在哪結束，得先掃一遍。但其實根本不用先知道 —— 讓遞迴自己走到那裡就好。
把索引改成一個單向前進、所有層共用的游標，規則只有三條：
- 讀完數字，游標停在數字後面
- 看到
(，吃掉它，遞迴下去 - 遞迴回來時，游標剛好停在配對的
)上，吃掉它
第 3 條是整個做法成立的關鍵：子函式讀到 ) 就會回傳（那是它的終止條件），所以它回來的時候，游標必定停在自己那對括號的收尾上。配對是遞迴自己完成的，不需要棧。
# 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 留下的那個 ()。進去之後立刻撞到 )，回傳 None，外層再把那個 ) 吃掉。
拿 4(2)(5) 走一遍，看游標怎麼單向推進：
動作 index
讀到 4 1
吃掉 ( 進左子樹 2
讀到 2 3
吃掉 ) 離開左子樹 4
吃掉 ( 進右子樹 5
讀到 5 6
吃掉 ) 離開右子樹 7
index 從 0 到 7 只往前走，沒有回頭過 —— 這就是 的來源。
代價是遞迴不再是純函式：它依賴並修改外層的 index，所以呼叫的順序有意義，root.left 那兩行和 root.right 那兩行絕對不能對調。前兩版把範圍當參數傳，反而沒有這個限制。
補充
共用游標這個手法在別的地方也出現過：394. Decode String 的遞迴版用的就是 nonlocal index，297 的前序反序列化則是用 deque 從左邊消耗。三題的心法是同一句：不要複製資料，也不要回頭重掃，只推進位置。
只用一個棧也能做，不用遞迴：掃字串時遇到數字就建節點掛到棧頂那個節點上（左邊沒滿掛左邊，否則掛右邊），遇到 ) 就 pop。我沒有用這個角度寫過，但那是這題的迭代解。
同一個題組：
| 題目 | 方向 | 格式 |
|---|---|---|
| 606 | 樹 → 字串 | 括號 |
| 536 | 字串 → 樹 | 括號 |
| 297 | 兩邊都要 | 自己選（哨兵最省事） |
| 449. Serialize and Deserialize BST | 兩邊都要 | 前序，不用哨兵 |
| 428. Serialize and Deserialize N-ary Tree | 兩邊都要 | 要多存「有幾個小孩」 |
整理見 Tree 遍歷模板。
複雜度
是字串長度、h 是樹高（平衡時 、斜樹 ）。
| 寫法 | 時間 | 空間 |
|---|---|---|
| 切片版 | — 每層都留著一份子字串 | |
| 傳索引版 | — 只有遞迴堆疊 | |
| 單一游標 |
前兩版的 都來自同一件事：每一層都要掃一遍才能找到括號的配對位置，而那一遍的長度就是這棵子樹的字串長度。 斜樹上 ，所以最壞是 。
傳索引沒有改變掃描次數，改變的是「有沒有真的把那段字串複製出來」—— 所以時間量級一樣，空間差很多。