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

2025-04-07 HGNULB 约 4 分钟

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

分类

LeetCode CodeTop 中等 未解决 1-2 字节

标签

字符串 深度优先搜索 树 二叉树

题目描述

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

题意分析

按先序顺序把二叉树写成“节点值(左子树)(右子树)”的字符串，同时省略多余空括号。省略后仍必须能唯一还原原树，尤其不能混淆只有左孩子与只有右孩子的情况。

解法：递归 DFS

核心思路

[!blue]
每个节点先输出自己的整数值，再用括号标记子树边界。第一组括号表示左子树，第二组表示右子树，所以空括号能否省略，取决于删掉后会不会改变左右含义。

叶子没有孩子，只输出值即可；只有左孩子时，输出左子树的一组括号，末尾的空右括号可以省略。右孩子存在时，两组括号都必须保留：左边即使为空，也要用 () 占住第一组，否则右子树会被当成左子树。

tree2str(node) 返回这棵子树本身的表示，不额外包裹整棵子树，外层括号由它的父节点添加。空节点返回空串，因此“左空右非空”无需单独拼特殊格式，父节点加上左右括号就会自然形成左侧占位。

代码先判断叶子，再判断右子树为空。进入后一个分支时，已经排除了左右都空的情况，因此左子树一定存在；剩余情况统一处理右子树存在，不会多写叶子的括号。

解题步骤

1. 空节点返回空串，叶子返回节点值。
2. 右侧为空时，仅拼接左子树括号。
3. 右侧存在时，依次拼出左右两组括号。
4. 返回当前子树的字符串。

代码实现

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) + ")";
    }
}

import "strconv"

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(nh)$ 上界，n 为节点数、h 为树高。子树字符串会在各祖先处被重新复制，链状树最坏为 $O(n²)$，不能仅按节点访问一次判断为线性时间。
• 空间复杂度：$O(n)$，包含输出、中间字符串与递归栈的峰值。

关键点总结

[!green]

• 左空右非空时必须保留左占位。
• 叶子分支先于仅右空分支，避免多余括号。
• 节点值按整数文本输出，支持多位数和负数。

易错点总结

[!yellow]

• 把所有空括号都删掉：仅右孩子会被误读成左孩子。
• 叶子仍输出两组括号：不是要求的简化表示。
• 空节点返回括号而非空内容：父层会多包一层。
• 左右拼接顺序交换：得到镜像结构。

相似题目

题目	难度	关联与区别
536. 从字符串生成二叉树	中等	互为括号树表示的构造与解析，本题省略空括号时仍要保留左右孩子身份。
297. 二叉树的序列化与反序列化	困难	同样需要编码保留树形，本题使用括号层级，通用序列化常用空位标记。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2025/91787614

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！