LeetCode 606. 根据二叉树创建字符串

2025-04-07 HGNULB 约 10 分钟

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

分类

题目描述

✅ 606. 根据二叉树创建字符串

题意分析

给一棵二叉树，把它序列化成字符串。规则是：先写节点值，再用一对括号包住左子树的字符串，再用一对括号包住右子树的字符串；同时要求在不影响还原出原树的前提下，省略掉所有可以省略的空括号。

「不影响还原」这五个字是全题的重心。如果不省略，格式就是死板的 val(左)(右)，写起来毫无难度；难点全在于判断哪一对空括号可以拿掉、哪一对必须留着。

逐一分析四种情形。左右都为空（叶子）：两对括号都是空的，写不写都能还原，全部省略，只留下节点值。只有左子树：右括号是空的，去掉之后剩下 val(左)，读者看到唯一一对括号——按规则第一对括号总是左子树——依然能正确还原，所以右侧空括号可省。只有右子树：如果把左侧的空括号也省掉，就变成 val(右)，与「只有左子树」的形态完全一样，产生歧义，所以左侧空括号必须保留，写成 val()(右)。左右都有：两对括号都非空，照写。

归纳出来只有一条规则：空括号能省的唯一条件是「它后面没有非空的括号了」。因为括号是靠位置来区分左右的，一旦右边有内容，左边的占位就不能丢。

约束方面，节点数是线性规模，每个节点在输出里贡献常数个字符，所以结果串长度是 $O(n)$，目标显然是一趟前序遍历。题目本身没有算法难度，考的是规则的完备性——能不能把四种情形不重不漏地列全，以及能不能讲清楚「为什么这一对能省、那一对不能」。

边界：根为空返回空串；节点值可能是负数（多个字符），拼接时要用值的字符串形式而不是单个字符；单节点树的输出就是它的值，不带任何括号。

解法：递归 DFS

核心思路

输出格式本身就是递归定义的——一棵树的字符串 = 根值 + 左子树的字符串（可能带括号）+ 右子树的字符串（可能带括号）。既然定义是递归的，直接照着写递归即可，不需要任何转化。

递归契约定为：tree2str(node) 返回以 node 为根的子树的完整字符串，不含包裹它自己的那对括号。括号由父节点在拼接时补上——这个分工必须固定。原因是「要不要括号」这件事只有父节点知道（它要看自己有没有右子树），子节点自己判断不出来。把职责划清，四种情形的处理就都落在同一层里，不会散落。

于是函数体就是对四种情形的直接翻译，且必须按下面的顺序判断：

第一，node == null 返回空串。这一条既处理「根为空」的入口边界，也让「左子树为空但要占位」的情形自动得到空串——父节点拼出 val()(右) 时，中间那个空串正是这一行返回的。

第二，左右都为空（叶子）返回节点值本身。两对括号都空且后面没有内容，全部省略。

第三，右子树为空（此时左子树必然非空，因为叶子情形已经在上一条被拦下）返回 val(左)。右侧空括号后面没有内容，可省。

第四，其余情形（右子树非空）返回 val(左)(右)。注意此时左子树可能为空，但因为右边有内容，左侧括号必须保留——而 tree2str(null) 恰好返回空串，拼出来自然就是 val()(右)，不需要为它写任何特殊分支。这是整段代码最精巧的一处：用「空节点返回空串」这一个约定，顺手覆盖了「左空右非空要留占位括号」这个看似棘手的情形。

判断顺序不能打乱。若把第三条（右空）放到第二条（叶子）之前，叶子节点会命中「右空」分支输出 val()，多出一对本该省略的空括号。四个分支形成的是一条从特殊到一般的链，每一条都依赖前面已经把更特殊的情形排除掉。

不变量：每次调用返回的字符串，恰好是该子树按题目规则序列化的最简形式，且不带外层括号。归纳可证：叶子显然成立；内部节点在子结果成立的前提下，按上述四条规则补括号，结果仍最简且无歧义。

解题步骤

第一行判 root == null 返回空串。为什么：一处代码承担两个职责——挡住空树入口，以及为「左空右非空」情形提供那个夹在 () 之间的空内容。有了它，后面不需要任何针对空左子树的特判。

第二判 left == null && right == null，返回节点值的字符串形式。为什么：叶子的两对括号都是空的，且后面没有任何内容，按「能省则省」全部去掉；这一条必须排在「右空」之前，否则叶子会被误认成「只有左子树」的情形而多出一对括号。用值的字符串形式而非字符，是因为节点值可能是多位数或负数。

第三判 right == null，返回 val + "(" + tree2str(left) + ")"。为什么：能走到这里说明左子树必然非空（叶子已被上一条排除），右侧的空括号后面没有内容、去掉不产生歧义，所以只写一对括号。

其余情形返回 val + "(" + tree2str(left) + ")(" + tree2str(right) + ")"。为什么：右子树非空，两对括号都必须写出；左子树若为空，tree2str(null) 返回空串，自动拼成 val()(右)，占位括号得以保留而不需要额外分支——这正是第一条约定带来的红利。

返回结果。

以树 1 → 左 2、右 3，其中 2 只有右孩子 4 走一遍（期望输出 1(2()(4))(3)）。

tree2str(1)：非空，左右都非空，命中第四条。先递归左子树。

tree2str(2)：非空；左为空、右非空，所以不是叶子，也不满足「右空」，命中第四条。递归左子树 tree2str(null) 得到空串 ""；递归右子树 tree2str(4)——节点 4 是叶子，命中第二条返回 "4"。拼接得 "2" + "(" + "" + ")(" + "4" + ")" 即 "2()(4)"。注意中间那对空括号：它不是靠任何特判写出来的，而是「空节点返回空串」自然产生的——正因为右边有 (4)，左边的占位必须保留，否则 2(4) 会被误读成「2 有一个左孩子 4」。

回到 tree2str(1)，再递归右子树 tree2str(3)——叶子，返回 "3"。

拼接得 "1" + "(" + "2()(4)" + ")(" + "3" + ")" 即 "1(2()(4))(3)"，与期望一致。

再看一个对照例子：把 4 从 2 的右孩子改成左孩子。此时 tree2str(2) 的左非空、右为空，命中第三条，返回 "2(4)"；整体输出 "1(2(4))(3)"。两棵结构不同的树分别得到 2()(4) 和 2(4)，正是那对空括号把它们区分开——这就是「左侧空括号不能省」的全部理由。

最后看边界 root = null：第一条直接返回空串；单节点树 [1]：命中第二条返回 "1"，不带任何括号。

代码实现

class Solution {
    public String tree2str(TreeNode root) {
        // 既挡住空树入口，也为「左空右非空」提供括号中间的空内容。
        if (root == null) {
            return "";
        }
        // 叶子：两对空括号后面都没有内容，全部省略。必须排在「右空」之前。
        if (root.left == null && root.right == null) {
            return String.valueOf(root.val);
        }
        // 走到这里左子树必非空；右侧空括号后无内容，可省。
        if (root.right == null) {
            return root.val + "(" + tree2str(root.left) + ")";
        }
        // 右子树非空：左侧括号必须占位，左空时上面的空串会自动拼出 val()(右)。
        return root.val + "(" + tree2str(root.left) + ")(" + tree2str(root.right) + ")";
    }
}

func tree2str(root *TreeNode) string {
    // 既挡住空树入口，也为「左空右非空」提供括号中间的空内容。
    if root == nil {
        return ""
    }
    // 叶子：两对空括号后面都没有内容，全部省略。必须排在「右空」之前。
    if root.Left == nil && root.Right == nil {
        return strconv.Itoa(root.Val)
    }
    // 走到这里左子树必非空；右侧空括号后无内容，可省。
    if root.Right == nil {
        return strconv.Itoa(root.Val) + "(" + tree2str(root.Left) + ")"
    }
    // 右子树非空：左侧括号必须占位，左空时上面的空串会自动拼出 val()(右)。
    return strconv.Itoa(root.Val) + "(" + tree2str(root.Left) + ")" + "(" + tree2str(root.Right) + ")"
}

复杂度分析

时间复杂度：$O(n \cdot h)$，n 为节点数、h 为树高；平衡树时为 $O(n \log n)$，链状树时退化为 $O(n^2)$。凭什么：每个节点被访问一次是 $O(n)$，但这份写法在每一层都用 + 拼接生成新字符串，一个字符会被它上方的每一层各复制一次，复制总量正比于「每个字符的深度之和」。若把拼接改成向一个共享的 StringBuilder 追加（递归时把它当参数传下去），复制就消失了，总时间降到 $O(n)$。这里保留拼接写法是因为它把四条规则表达得最直白，面试白板上更好讲；被追问性能时说出上面的优化即可。

空间复杂度：$O(n)$。凭什么：递归栈深度等于树高 $O(h)$，最坏 $O(n)$；输出字符串长度是 $O(n)$（每个节点贡献值本身加至多四个括号字符）；拼接过程中产生的中间字符串会被逐层丢弃，峰值同样是 $O(n)$ 量级。

关键点总结

序列化题的核心永远是歧义分析：先问「省掉这部分之后，还能不能唯一还原」。本题的全部规则都由这一条推出——左括号靠位置区分左右孩子，所以右边有内容时左边的占位不能丢。

把四种情形（都空 / 只左 / 只右 / 都有）列成表逐一判断，是保证不重不漏的笨办法，也是最可靠的办法。面试时先在白板上列这张表，再翻译成代码，比边想边写稳得多。

分支的判断顺序本身是逻辑的一部分：必须从最特殊排到最一般，每条分支都默认前面更特殊的情形已被排除。把「叶子」放在「右空」之后，叶子就会多出一对空括号。

让空节点返回空串，然后用它自然拼出必需的占位括号，是本题最漂亮的一手：一个约定同时解决了入口边界和「左空右非空」这个看似要特判的情形。凡是递归返回字符串或集合，都值得想想「空值能不能承担占位职责」。

递归契约要划清「括号由谁来加」。子节点不知道自己该不该被括起来，只有父节点知道，所以子函数一律返回不带外层括号的结果——职责边界一旦模糊，四种情形就会散落到两层里，很难写对。

面试延伸：被问性能时指出「层层拼接导致 $O(n \cdot h)$，改用共享 StringBuilder 追加可降到 $O(n)$」；被问「怎么反过来解析」时，指向 536 题——那是本题的逆运算，用共享游标做递归下降。

易错点总结

左子树为空、右子树非空时省略了左侧空括号：树 2 只有右孩子 4 → 输出 2(4)，与「2 只有左孩子 4」的结果完全相同，无法还原，正确输出是 2()(4)。

无条件写出两对括号、不做任何省略：单节点树 [1] → 输出 1()()，而正确答案是 1；叶子节点的空括号必须省。

把「右子树为空」的判断放在「叶子」之前：叶子节点 → 命中右空分支输出 1()，多出一对本该省略的括号。

忘记 root == null 的判断：tree2str(null) → 直接访问 root.left 抛空指针；而且「左空右非空」时也拿不到那个空串，占位括号无从生成。

空节点返回 "()" 而不是空串：树 1 只有右孩子 2 → 输出 1(())(2)，凭空多出一层括号。

左右子树的递归顺序写反：树 1(2)(3) → 输出 1(3)(2)，还原出来的是镜像树。

用 (char)(root.val + '0') 之类的方式转换节点值：节点值为 12 或 -4 → 转换出乱码字符，只有单个数字的树才恰好正确。

在「右空」分支里仍然拼上右侧的空括号：树 1(2) → 输出 1(2)()，不是最简形式，判题失败。

把括号由子节点自己添加：子函数返回 "(" + ... + ")" → 父节点无法根据自己有没有右孩子来决定省略，四种情形的判断逻辑被拆到两层，右侧空括号省不掉。

在链状树上用层层拼接却不注意规模：$10^4$ 个节点的左偏树 → 每个字符被复制约 $10^4$ 次，字符复制总量到 $10^8$ 量级，可能超时；改用共享 StringBuilder 追加即可。

相似题目

题目	难度	考察点
536. 从字符串生成二叉树	中等	本题的逆运算，用共享游标做递归下降解析，难点从「省略」变成「定位」
297. 二叉树的序列化与反序列化	困难	格式自定且必须成对实现，通常显式写出空节点占位符，反而不需要歧义分析
449. 序列化和反序列化二叉搜索树	中等	可利用 BST 的有序性省掉空节点标记，是「靠额外性质压缩编码」的典型
331. 验证二叉树的前序序列化	中等	只判断格式是否合法而不建树，用槽位计数一趟扫描即可
144. 二叉树的前序遍历	简单	同为「根 → 左 → 右」的访问顺序，但只收集值、不涉及结构信息的编码
428. 序列化和反序列化 N 叉树	困难	孩子个数不定，必须写出孩子数或用分隔符，括号的位置语义不再够用
394. 字符串解码	中等	同为括号嵌套结构，但括号前带重复次数，递归产出的是展开后的字符串
1367. 二叉树中的链表	中等	同为前序框架下的结构匹配，考的是「从任意节点重新起匹配」的分支处理