LeetCode 536. 从字符串生成二叉树
题目描述
题意分析
输入先写当前节点的整数值，随后用括号包住它的子树，按左子树、右子树的顺序出现。子树内部仍采用同一种格式；整数可能为负数或多位数，整个输入为空字符串时返回空树。
空括号表示这一侧没有节点。有右子树而没有左子树时，需要保留左侧的空括号，才能让后面的括号仍然对应右子树。空子树不能被当成值为
0的节点。字符串结构与树结构递归对应。解析完根值后，遇到一组子树括号就交给递归处理，让子调用返回节点并告知读到了哪里，父层便能继续处理下一组子树。
解法：递归解析括号
核心思路
[!blue]
递归负责解析一棵子树，共享游标记录消费位置。i指向下一个尚未消费的字符。进入dfs时先判断是否为空：已经到达串尾，或当前位置直接是右括号，说明没有节点内容，应返回空节点。右括号仍留给打开它的父层消费，不能在判空时额外推进游标。非空时再读取节点值：先读取可选负号，再用
val = val * 10 + digit连续累积数字，直到遇到括号或串尾，随后创建当前节点。先判空再读数，才能区分没有节点与数值恰好为零的真实节点。如果后面紧跟左括号，父层先越过它，再调用
dfs解析左子树。子调用只消费子树自身的值和内部括号，返回时停在包裹这棵子树的右括号前；父层再把它越过。左右括号由同一层负责，嵌套范围便由递归调用自然匹配，不必反复搜索对应右括号。处理完第一组后，再独立检查一次左括号，若存在就按相同方式解析右子树。不能写成互斥分支，因为同一个节点可能有左右两棵子树。若没有后续左括号，当前节点的内容就已经结束，直接把节点返回给父层。
空子树不消费包裹它的右括号，叶节点只消费自己的整数，这两种递归边界都满足游标契约。若左右子调用也能正确返回节点和结束位置，父层就能把它们接到正确方向，并停在自己的结束位置。因此从根调用可以逐层还原整棵树。
Java 的
i是对象成员，公开入口每次先重置为零；Go 的i是本次调用中由闭包共享的局部变量。子层推进后的下标都能被父层继续使用，多次调用也不会沿用上一次的读取位置。
解题步骤
- 初始化游标，调用递归；到达串尾或直接遇到右括号时，返回空节点。
- 读取符号和完整整数，创建当前节点。
- 若后面有第一组括号，递归解析左子树并跨过对应右括号。
- 继续检查第二组括号并解析右子树，返回当前节点。
代码实现
class Solution {
// i 跨递归层共享：子层消费到哪里，父层必须看得见。
private int i;
public TreeNode str2tree(String s) {
i = 0;
return dfs(s);
}
// 契约：进入时 i 指向子树起始位置，返回时停在外层右括号或串尾。
private TreeNode dfs(String s) {
if (i == s.length() || s.charAt(i) == ')') {
return null;
}
int sign = 1;
if (s.charAt(i) == '-') {
sign = -1;
i++;
}
int val = 0;
// 数值可能是多位数，必须一次读完。
while (i < s.length() && Character.isDigit(s.charAt(i))) {
val = val * 10 + (s.charAt(i) - '0');
i++;
}
TreeNode node = new TreeNode(sign * val);
// 第一对括号必然是左子树：谁开的括号谁关。
if (i < s.length() && s.charAt(i) == '(') {
i++;
node.left = dfs(s);
i++;
}
// 独立的 if 而非 else：左右子树可以同时存在。
if (i < s.length() && s.charAt(i) == '(') {
i++;
node.right = dfs(s);
i++;
}
return node;
}
}
func str2tree(s string) *TreeNode {
// i 由闭包捕获，跨递归层共享。
i := 0
// 契约：进入时 i 指向子树起始位置，返回时停在外层右括号或串尾。
var dfs func() *TreeNode
dfs = func() *TreeNode {
if i == len(s) || s[i] == ')' {
return nil
}
sign := 1
if s[i] == '-' {
sign = -1
i++
}
val := 0
// 数值可能是多位数，必须一次读完。
for i < len(s) && s[i] >= '0' && s[i] <= '9' {
val = val*10 + int(s[i]-'0')
i++
}
node := &TreeNode{Val: sign * val}
// 第一对括号必然是左子树：谁开的括号谁关。
if i < len(s) && s[i] == '(' {
i++
node.Left = dfs()
i++
}
// 独立的 if 而非 else：左右子树可以同时存在。
if i < len(s) && s[i] == '(' {
i++
node.Right = dfs()
i++
}
return node
}
return dfs()
}
复杂度分析
- 时间复杂度：$O(L)$，L 为字符串长度，游标只向前推进。
- 空间复杂度：辅助递归栈 $O(h)$，h 为树高；输出节点另占 $O(n)$。
关键点总结
[!green]
- 递归返回节点，同时通过共享游标传递结束位置。
- 包裹子树的左右括号由父层消费，子层只解析自身内容。
- 空子树只返回空节点，不创建节点，也不消费父层的右括号。
- 数字连续读取到结束，不能只读取一位。
易错点总结
[!yellow]
- 左右子树使用 if/else if：解析左侧后不会继续检查右侧。
- 读到数字后忘记推进游标：循环不能结束。
- 对子树结束的右括号重复跳过：父子层的消费边界错位。
- Java 多次调用不重置成员游标：下一次解析从旧位置开始。
- 空子树若直接进入读数逻辑，会把默认值
0错当成真实节点；必须先根据游标位置判空。- 空子树返回后仍由父层跳过右括号，不能因判空再多跳一次，否则后面的右子树会错位。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 297. 二叉树的序列化与反序列化 | 困难 | 两题都从编码还原树，本题左右子树由括号层级界定，常见序列化还会显式记录空位。 |
| 385. 迷你语法分析器 | 中等 | 同样递归解析括号嵌套，本题每个节点最多两个子树，原题是任意长度的整数列表。 |