企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇技术指南围绕「LeetCode 0606. 根据二叉树创建字符串」展开，讲解如何通过前序遍历（Preorder Traversal）配合深度优先搜索（DFS），把一棵二叉树转换成一个由括号和整数组成的字符串，并重点剖析「何时必须保留空括号"()"、何时可以省略」这一核心规则。读完本文，你将掌握该题的四条括号构造规则、可直接运行的 Python 递归解法、递归调用链的逐步推演，以及时间/空间复杂度分析；该题也是 二叉树遍历 与 字符串处理 两类基础能力的综合应用。

1. 题目概览

1.1 题目链接与基础信息

• 题目编号：0606. 根据二叉树创建字符串（Construct String from Binary Tree）
• 标签：树、深度优先搜索、字符串、二叉树
• 难度：中等
• 题解原文：docs/solutions/0600-0699/construct-string-from-binary-tree.md

1.2 题目大意

给定二叉树的根节点root，要求：

采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，并返回构造出的字符串。

其中空节点使用一对空括号对"()"表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

1.3 数据范围约束

• 树中节点的数目范围是 $[1, 10^{4}]$；
• 节点取值满足 $-10^{3} \le Node.val \le 10^{3}$。

节点规模最多可达 $10^4$，意味着任何 $O(n^2)$ 级别以上的实现都可能超时，只有线性级别的遍历方案是安全的；同时节点值为负数时需要正确处理负号与括号的位置关系。

2. 示例逐层拆解

2.1 示例 1：右子树为空时省略括号

输入：root = [1,2,3,4] 输出："1(2(4))(3)"

解释：若不做任何省略，初步转化会得到"1(2(4)())(3()())"，即每个左/右子位置都用括号对补齐。但观察节点2：它有左孩子4、右孩子为空，此时右孩子位置的空括号对"()"并不影响字符串与二叉树的一一对应，可以省略；节点3左右孩子均为空，它的"()()"同样可以完全省略。最终字符串为"1(2(4))(3)"。

2.2 示例 2：左子树为空时不能省略

输入：root = [1,2,3,null,4] 输出："1(2()(4))(3)"

解释：节点2没有左孩子、但有右孩子4。此时左孩子位置的空括号对"()"不能省略——一旦省略，字符串会变成"1(2(4))(3)"，与示例 1 的输出完全相同，就无法区分「4是2的左孩子」还是「4是2的右孩子」，从而破坏字符串与二叉树的一对一映射关系。

3. 核心解题思路：前序遍历 + DFS

3.1 为什么用前序遍历

前序遍历的顺序是「根节点 → 左子树 → 右子树」（详见 二叉树前序遍历）。本题要求「采用前序遍历的方式」构造字符串，因此递归时总是先输出当前节点值，再递归处理左子树、右子树，这与标准的二叉树前序遍历递归框架完全一致：

def preorder(node): if not node: return # 1. 访问根节点 # 2. 递归遍历左子树 # 3. 递归遍历右子树

本题只是在「访问根节点」后，将左右子树的递归结果用括号包裹并拼接成字符串。

3.2 括号省略的完整规则

题解 construct-string-from-binary-tree.md 总结出四条规则，它们是本题的唯一难点，务必牢记：

等价地概括：只要存在右子树，就必须先输出左位置的括号对（左子树为空时输出"()"）；只要存在左子树，右位置为空时可以省略右括号对。

3.3 为什么左空右非空时必须补"()"

从字符串的形态上可以直观验证：

• "1(2(4))(3)"中，4被解析为2的左孩子；
• "1(2()(4))(3)"中，()占据左孩子槽位，4被解析为2的右孩子。

正是这个「占位空括号」保留了孩子位置的语义，保证了双向唯一的映射：给定二叉树可唯一生成字符串，给定字符串也能唯一还原二叉树（这正是 LeetCode 上「根据二叉树创建字符串」与 0652. 寻找重复的子树 等序列化类题目共同依赖的性质）。

4. 完整可运行代码

以下为题解原文提供的 Python 实现（基于TreeNode定义，Optional来自typing）：

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def tree2str(self, root: Optional[TreeNode]) -> str: if not root: return "" # 只有根节点 if not root.left and not root.right: return str(root.val) # 有左子树，没有右子树 if root.left and not root.right: return str(root.val) + "(" + self.tree2str(root.left) + ")" # 有右子树（无论是否有左子树） return str(root.val) + "(" + self.tree2str(root.left) + ")(" + self.tree2str(root.right) + ")"

4.1 代码与规则的一一对应

注意最后一个分支的精妙之处：当左子树为空时，self.tree2str(root.left)返回""，拼接后得到str(root.val) + "()" + "(" + 右子树串 + ")"，空括号"()"被自动生成，无需显式特判，这正是示例 2 中"1(2()(4))(3)"的由来。

4.2 递归调用链逐步推演（示例 1）

以root = [1,2,3,4]为例：

1. tree2str(1)：有左孩子2、右孩子3，进入末尾分支 →"1" + "(" + tree2str(2) + ")" + "(" + tree2str(3) + ")"；
2. tree2str(2)：有左孩子4、无右孩子，进入第二分支 →"2" + "(" + tree2str(4) + ")"；
3. tree2str(4)：叶子节点 →"4"；
4. tree2str(3)：叶子节点 →"3"。

自底向上回代得到："1" + "(2(4))" + "(3)" = "1(2(4))(3)"，与预期输出一致。

5. 复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是二叉树的节点数。递归过程中每个节点被访问且仅被访问一次，每次访问只做常数次字符串拼接与判断。
• 空间复杂度：$O(n)$。递归调用栈的深度在最坏情况下（退化为链状的单支树）可达 $n$；同时每次拼接都会产生新的中间字符串，累计的临时字符串开销也为 $O(n)$。

作为对照，二叉树遍历 中给出的标准前序遍历时间复杂度同为 $O(n)$、空间复杂度为 $O(h)$（$h$ 为树高，最坏 $O(n)$），本题与其一致，说明该解法在 $10^4$ 节点规模下是安全且最优的。

6. 易错点与边界情况小结

1. 负数节点值：如-10，str(root.val)得到"-10"，拼接规则不变，括号始终包裹在子树字符串外层，不会出现歧义；
2. 单节点树：root = [1]输出"1"，走叶子分支，不加任何括号；
3. 只有左链的树：root = [1,2,null,3]输出"1(2(3))"，每一层都省略右侧空括号；
4. 只有右链的树：root = [1,null,2,null,3]输出"1()(2()(3))"，每一层都必须保留左侧"()"占位——这是最容易写错的场景；
5. 空左补"()"是区分左右孩子的唯一手段：删掉它会直接导致字符串与二叉树失去一对一映射，违背题意。

7. 进一步延伸

本题属于「二叉树的序列化」家族，掌握括号省略规则后，可进一步阅读仓库中相关题解加深理解：

• 0652. 寻找重复的子树：需要为每棵子树生成规范化字符串，本质是同一套序列化思维的运用；
• 0654. 最大二叉树 与 0655. 输出二叉树：从数组/二叉树反方向的构造与可视化，可与本题互为对照；
• 若希望系统复习前序遍历的递归与非递归（显式栈）两种写法，可回到 二叉树遍历 章节，其「先右后左入栈」的迭代框架同样可以改造成本题的迭代解法；
• 题目索引可参考 0600-0699 题解索引 与 题解总列表。

• 教程
• 文档
• 知识库