【码道初阶】【Leetcode606】二叉树转字符串：前序遍历 + 括号精简规则，一次递归搞定

【Leetcode606】二叉树转字符串：前序遍历 + 括号精简规则，一次递归搞定

题目要求把一棵二叉树转成字符串，形式类似：

• 节点值直接输出
• 左子树用(left)包起来
• 右子树用(right)包起来
• 空节点一般用()表示
• 但要省略所有不影响一一映射的空括号

这句话很关键：

“省略不影响一一映射关系的空括号”
意味着：省略不能让结构变得模糊。

1）先把规则讲明白（这是整题的灵魂）

对于一个节点root：

情况 A：有左子树

输出：root(left...)

• 左子树的括号不能省略，因为它告诉读者“左边有东西”。

情况 B：没有左子树，但有右子树

输出：root()(right...)

• 这里左边必须输出()
  因为如果省掉()，例如写成root(right...)，读者会误以为右子树其实是左子树，结构就对不上了。
  这就是示例 2 的核心原因。

情况 C：没有右子树

• 右子树这一对括号可以省略（因为右边啥都没有，省了不会产生歧义）。

总结成一句口诀：

右子树存在而左子树不存在时，左边的空括号必须保留；除此之外，能省则省。

2）整体解题思路（递归前序遍历）

用前序遍历（根→左→右）去拼字符串：

1. 访问当前节点：拼接root.val

2. 处理左子树括号：

   • 左不空：拼(+ 左子树 +)
   • 左空但右不空：拼()

3. 处理右子树括号：

   • 右不空：拼(+ 右子树 +)
   • 右空：不拼（直接省略）

为了高效拼字符串，用StringBuilder，避免大量字符串相加造成性能浪费。

3）来看这段代码（整体结构）

classSolution{publicStringtree2str(TreeNoderoot){StringBuilderstringbuilder=newStringBuilder();tree2strchild(root,stringbuilder);returnstringbuilder.toString();}publicvoidtree2strchild(TreeNoderoot,StringBuilderstringbuilder){if(root==null)return;stringbuilder.append(root.val);if(root.left!=null){stringbuilder.append("(");tree2strchild(root.left,stringbuilder);stringbuilder.append(")");}else{if(root.right==null)return;stringbuilder.append("()");}if(root.right!=null){stringbuilder.append("(");tree2strchild(root.right,stringbuilder);stringbuilder.append(")");}else{return;}}}

这份实现是典型的“在递归时直接把括号拼出来”，没有额外数组、栈，空间开销只有递归深度。

4）逐步拆解代码逻辑（每一段在干嘛）

4.1 递归出口：空节点直接返回

if(root==null)return;

空节点不输出任何字符。注意题目里说“空节点用 () 表示”，但那是“表示空孩子”的概念，并不是说碰到 null 就无脑输出()——是否输出()取决于父节点规则（尤其是“左空右不空”的场景）。

4.2 先输出当前节点值（前序的“根”）

stringbuilder.append(root.val);

这一步就是“根”。

4.3 处理左子树（左括号是否要输出）

if(root.left!=null){stringbuilder.append("(");tree2strchild(root.left,stringbuilder);stringbuilder.append(")");}else{if(root.right==null)return;stringbuilder.append("()");}

分两类情况：

左子树存在

输出：(left...)

也就是：

• 先拼(
• 递归拼左子树内容
• 再拼)

左子树不存在

这里又分两种：

• 如果右子树也不存在：直接return

  • 因为左右都空，当前节点已经输出完了，不需要额外括号

• 如果右子树存在：必须输出()

  • 这是保留“一一映射”的关键：告诉读者“左边是空的，右边才有东西”

这段代码准确实现了规则 B 和规则 C。

4.4 处理右子树（右括号是否要输出）

if(root.right!=null){stringbuilder.append("(");tree2strchild(root.right,stringbuilder);stringbuilder.append(")");}else{return;}

右子树存在就输出(right...)；不存在直接省略（return 结束当前节点处理）。

5）用示例走一遍：为什么会输出正确结果？

示例 1：root = [1,2,3,4]

结构是：

1 / \ 2 3 / 4

递归过程（按拼接顺序）：

• 访问 1：输出1

• 左存在：输出( ... )

  • 访问 2：输出2

  • 左存在：输出( ... )

    • 访问 4：输出4
    • 4 左空右空：直接结束，不加括号

  • 2 右空：省略

• 右存在：输出( ... )

  • 访问 3：输出3
  • 3 左空右空：结束

最终：1(2(4))(3)✅

示例 2：root = [1,2,3,null,4]

1 / \ 2 3 \ 4

关键节点是 2：

• 2 左空，但右不空（有 4）
• 必须输出2()(4)

如果省略()，会变成2(4)，读者会理解成“4 是 2 的左孩子”，结构就错了。

这就是题目强调“一对一映射”时()必须保留的唯一典型场景。

6）复杂度分析

• 时间复杂度：O(n)
  每个节点访问一次，拼接一次（括号是常数次追加）
• 空间复杂度：O(h)
  递归栈深度，h为树高；极端退化链表时最坏O(n)

7）易错点重点提醒（写这题最常翻车的地方）

1. 不是所有 null 都输出()
()是由父节点决定是否需要表达空左孩子的。

2. “左空右不空”时必须输出()
   否则结构信息丢失，无法保持一一映射。

3. 字符串拼接别用+反复连
   这题节点最多 10^4，用StringBuilder是更稳的选择。

8）小结

这题的正确解法可以概括为一句话：

前序遍历输出节点值，左右子树用括号包裹；只有在“左空右不空”时必须补()，其余空括号能省则省。

把这个规则记牢，代码就会写得非常顺，且不容易漏掉示例 2 这种“最爱卡人”的用例。