LeetCode 536. 从字符串生成二叉树

2022-09-30 HGNULB 约 11 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 536. 从字符串生成二叉树

题意分析

给一个用括号表示的字符串 s，把它还原成二叉树。字符串的构成规则是：先写节点的整数值，然后依次用一对括号包住左子树、再用一对括号包住右子树；子树为空时对应的括号整个省略。例如 4(2(3)(1))(6(5)) 表示根为 4，左子树根为 2（有左孩子 3、右孩子 1），右子树根为 6（只有左孩子 5）。

这个格式里藏着两个必须看清的性质。第一，它是完全无歧义的递归定义：括号内部又是一个同样格式的字符串，所以整个解析过程天然是递归的，不需要任何回溯或猜测。第二，空子树是靠「括号缺席」表示的，而不是空括号。这意味着当只有一个括号跟在数值后面时，它必然属于左子树——不存在「只有右孩子」的写法，右孩子必须由第二对括号承载。这条规则决定了解析时两个 if 的顺序不能颠倒、也不能写成 else if。

数值部分可能带负号（题目允许节点值为负），所以读数字前要先看一眼是不是 -。数值也可能是多位数，必须一直读到非数字字符为止，一次只读一个字符会把 123 拆成三个节点。

约束层面，字符串长度是线性规模且格式保证合法，说明不需要做容错校验，只要一趟从左到右扫描即可，目标复杂度是 $O(n)$。「必须一趟扫完、且子结构自相似」这两点合起来，指向「一个全局推进的下标 + 递归」的解析框架。

边界：s 为空串时返回空树；单个数字（如 -4）是一棵只有根的树；解析过程中每次进入括号要吃掉 (、返回时要吃掉 )，这两次「吃字符」必须成对，否则下标会整体错位、后续解析全盘崩塌。

解法：递归解析括号

核心思路

直觉上会想到「先用括号匹配把字符串切成三段——数值、左子树串、右子树串——再对两段分别递归」。这个思路正确，但每层都要从当前位置向右扫描去找配对的右括号，最坏情况（左偏树）下每层扫描 $O(n)$，总共退化到 $O(n^2)$；而且切子串还要额外的内存拷贝。

瓶颈在于重复扫描：为了找配对括号而走过的字符，进入递归后又要再走一遍。既然每个字符最终都恰好要被解析一次，那就干脆只走一遍——用一个在所有递归层之间共享的下标 i 表示「当前读到哪里」，每个递归层只负责把属于自己的那一段消费掉，然后把 i 留在下一段的开头。这样每个字符只被读一次，总复杂度降到 $O(n)$，也不需要任何子串拷贝。

这里的关键是把 i 提成成员变量（Go 里用闭包捕获），而不能作为参数按值传递——按值传递时子递归对 i 的推进无法反馈给父层，父层不知道左子树消费到了哪里，也就找不到右子树的起点。

于是每一层 dfs 的职责固定为三步：读出本节点的整数值（含可能的负号和多位数字）；若下一个字符是 (，说明有左子树，跨过 (、递归、再跨过 )；若此时下一个字符还是 (，说明有右子树，同样处理。做完返回本层节点。

递归契约（也就是这段代码的不变量）必须写清楚：调用 dfs 时 i 指向一棵子树表示串的第一个字符；dfs 返回时 i 恰好指向这棵子树表示串之后的第一个字符（可能是 )，也可能是字符串末尾）。只要每层都遵守这个契约，父层就能靠「看一眼 s[i] 是不是 (」来判断还有没有下一棵子树，整套解析自然成立。

最后注意两个 if 必须都写成独立的 if 而不是 if...else：一个节点可以同时有左右两棵子树，两段括号要连着处理。而顺序上先左后右，是因为格式规定第一对括号永远是左子树。

解题步骤

把下标 i 声明为跨递归层共享的状态，并在入口重置为 0。为什么：解析要求「每个字符只读一次」，子层消费到哪里必须让父层看得见；重置是因为同一个 Solution 实例可能被判题复用，残留的旧下标会让第二次调用直接越界。

入口先判 s 为空则返回空树。为什么：dfs 第一行就要读 s.charAt(i)，空串会直接越界；把这个唯一的非法输入挡在门外，dfs 内部就可以假定「进来时至少有一个字符」。

dfs 第一步：若当前字符是 -，记下负号并把 i 前移一位。为什么：节点值可以为负，符号必须在读数字前处理；只有紧跟在子树开头的 - 才是符号，读完数字后不会再遇到它。

循环读取连续数字，用 val = val * 10 + (c - '0') 累积，直到遇到非数字。为什么：数值可能是多位数，必须一次读完；以「非数字」作为终止条件而不是以 ( 作为终止条件，可以同时正确处理后面跟 ) 或字符串结束这两种情况。

用 sign * val 建出当前节点。为什么：节点必须在解析子树之前建好，因为子树要挂在它身上；同时这一步之后 i 恰好停在本节点数值之后，进入了「判断有没有子树」的状态。

若 i 未越界且 s[i] == '('：i++ 跨过左括号，递归得到左子树，返回后再 i++ 跨过右括号。为什么：递归契约要求进入 dfs 时 i 指向子树串首字符，所以必须先跨过 (；返回时按契约 i 停在 ) 上，父层负责把它吃掉——「谁开的括号谁关」这个分工必须固定，否则下标会错位。

再判一次 i 未越界且 s[i] == '('，同样处理右子树。为什么：写成第二个独立的 if 而不是 else，因为左右子树可以同时存在；能走到这里说明左括号已经成对消费完，此刻的 ( 只可能是右子树的开始。

返回当前节点。为什么：此时 i 恰好停在本子树之后，契约得以维持，父层可以安全地继续判断。

以 s = "4(2(3)(1))(6(5))" 走一遍（下标从 0 开始）。入口 i = 0，串非空，进入 dfs。

第 1 层：读到 4，i 推到 1，建节点 4。s[1] == '('，i 变 2，递归解析左子树。

第 2 层：读到 2，i 推到 3，建节点 2。s[3] == '('，i 变 4，递归。第 3 层读到 3，i 推到 5，建节点 3；s[5] == ')' 不是 (，两个 if 都不进，返回节点 3，此时 i = 5 正停在 ) 上——契约成立。回到第 2 层，把左孩子挂上，i++ 吃掉 ) 变成 6。s[6] == '('，i 变 7，递归解析右子树：读到 1，i 推到 8，返回节点 1。第 2 层挂上右孩子，i++ 吃掉 ) 变成 9。此时 s[9] == ')'，不是 (，第 2 层返回节点 2（带着孩子 3 和 1），i = 9。

回到第 1 层：挂上左孩子 2，i++ 吃掉 ) 变成 10。s[10] == '('，进入第二个 if，i 变 11，递归解析右子树：读到 6，i 推到 12；s[12] == '('，i 变 13，再递归读到 5，i 推到 14，返回节点 5；挂为 6 的左孩子，i++ 吃掉 ) 变成 15；s[15] == ')' 不是 (，返回节点 6。第 1 层挂上右孩子，i++ 吃掉 ) 变成 16，已到串尾，两个 if 的越界判断都不通过，返回根节点 4。

整棵树正确还原，且 i 恰好走完全串一次。注意节点 6 那里：它只有左孩子 5，对应的串是 6(5)——正因为「单个括号必属左子树」，才能在没有任何额外标记的情况下判断出 5 是左孩子而不是右孩子。

代码实现

class Solution {
    // i 跨递归层共享：子层消费到哪里，父层必须看得见。
    private int i;

    public TreeNode str2tree(String s) {
        i = 0;
        if (s.length() == 0) {
            return null;
        }
        return dfs(s);
    }

    // 契约：进入时 i 指向子树串首字符，返回时 i 指向该子树之后的第一个字符。
    private TreeNode dfs(String s) {
        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 {
	if len(s) == 0 {
		return nil
	}
	// i 由闭包捕获，跨递归层共享。
	i := 0

	// 契约：进入时 i 指向子树串首字符，返回时 i 指向该子树之后的第一个字符。
	var dfs func() *TreeNode
	dfs = func() *TreeNode {
		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(n)$，n 为字符串长度。凭什么：下标 i 只增不减，每个字符恰好被读一次——数字字符在读数循环里被消费，括号字符被 i++ 跨过，负号被符号判断消费；递归层数虽多，但所有层加起来对 i 的推进总量就是 n。

空间复杂度：辅助空间为 $O(h)$，h 是树高，来自递归栈；链状树时最坏为 $O(n)$。除此之外只有共享游标和每层的几个标量。返回的树本身占 $O(n)$，不计入辅助空间。

关键点总结

递归下降解析的标准骨架就是「共享一个游标 + 每层只消费自己那一段」。凡是遇到自相似的括号 / 嵌套结构，先定下这个骨架，再考虑细节。

必须显式写出递归契约：进入时游标在哪、返回时游标在哪。面试时把这句话说出来，等于同时给出了正确性证明和调试指南——所有下标错位的 bug 都是违反契约导致的。

游标要跨层共享（成员变量或闭包捕获），不能按值传参。这是「一趟扫描 $O(n)$」与「反复找配对括号 $O(n^2)$」的分水岭。

「空子树用括号缺席表示」推出「第一对括号必是左子树」。识别出这条隐含规则，两个 if 的顺序和独立性就都有了依据。

读数值时要同时处理负号和多位数，终止条件用「非数字」而不是「遇到某个特定字符」，这样对串尾和 ) 两种收尾都自动正确。

易错点总结

把 i 作为参数按值传给 dfs："4(2)(6)" → 解析完左子树后父层的 i 仍停在 2 的位置，右子树的括号被当成左子树重新解析，结果树结构错乱甚至无限递归。

两个 if 写成 if...else if："4(2)(6)" → 只解析出左孩子 2，右孩子 6 被完全忽略，且 i 停在中间。

两个 if 顺序颠倒（先挂右后挂左）："6(5)" → 5 被挂成右孩子，而正确答案是左孩子，结构镜像出错。

忘记处理负号："-4(2)" → 第一行读数循环遇到 - 立刻退出，val 为 0，建出值为 0 的节点，随后 s[i] 是 - 也不是 (，直接返回，整棵子树丢失。

一次只读一位数字："123" → 建出值为 1 的节点，后面的 23 无人消费，返回的树只有一个错误节点。

递归返回后忘记 i++ 跨过 )："4(2)(6)" → 左子树返回时 i 停在 )，第二个 if 判断 s[i] == '(' 失败，右孩子 6 丢失。

进入递归前忘记 i++ 跨过 (："4(2)" → dfs 第一行读到的是 ( 而不是数字，val 为 0，建出多余的 0 节点并陷入错误的解析路径。

if 里漏掉 i < s.length() 的越界判断："4" → 读完数值后 i 已等于长度，直接访问 s.charAt(i) 抛 StringIndexOutOfBoundsException。

用「找配对右括号后切子串再递归」的写法："1(2(3(4(5))))" 这类链状输入 → 每层都要向右扫到底，总时间退化成 $O(n^2)$，长串上超时；同时大量 substring 拷贝额外吃掉 $O(n^2)$ 内存。

空串未提前返回：s = "" → dfs 第一行 s.charAt(0) 越界崩溃，而正确答案是空树。

相似题目

题目	难度	考察点
606. 根据二叉树创建字符串	中等	本题的逆运算，难点转为「何时可以省略空括号」而非如何解析
297. 二叉树的序列化与反序列化	困难	编码格式由自己设计，空节点要显式写出占位符，解析反而比本题简单
394. 字符串解码	中等	同为括号嵌套的递归下降，但产出是展开后的字符串，且括号前带重复次数
385. 迷你语法分析器	中等	嵌套结构是列表而非二叉树，分隔符是逗号，同一层可以有任意多个子项
224. 基本计算器	困难	括号之外还要处理运算符优先级与正负号，解析同时要完成求值
1106. 解析布尔表达式	困难	括号前的操作符决定子结果如何归并，递归返回的是布尔值而非节点
726. 原子的数量	困难	括号后带乘数需要把整个子结果按倍数放大，还要对结果排序输出
105. 从前序与中序遍历序列构造二叉树	中等	同样是重建二叉树，但结构信息来自两个序列的交叉定位而非括号
331. 验证二叉树的前序序列化	中等	只需判断格式合法性而不必真正建树，可用槽位计数一趟扫描