Medium

题目描述

给定二叉树的根节点，你需要按照特定的格式规则构造一个字符串来表示整个二叉树。表示应该基于二叉树的前序遍历，并且必须遵循以下准则：

节点表示：树中的每个节点都应该由其整数值表示。

子节点的括号：如果节点有至少一个子节点（左子节点或右子节点），其子节点应该用括号表示。具体来说：

  • 如果节点有左子节点，左子节点的值应该紧跟在该节点值后面的括号中。
  • 如果节点有右子节点，右子节点的值也应该用括号括起来。右子节点的括号应该跟在左子节点的括号后面。

省略空括号：任何空括号对（即()）都应该从树的最终字符串表示中省略，但有一个特殊例外：当节点有右子节点但没有左子节点时。在这种情况下，必须包含一对空括号来表示左子节点的缺失。这确保了字符串表示和原始二叉树结构之间的一对一映射关系。

总之，当节点只有左子节点或没有子节点时，应该省略空括号对。但是，当节点有右子节点但没有左子节点时，必须在右子节点的表示前面加上一对空括号，以准确反映树的结构。

示例 1:

输入: root = [1,2,3,4]
输出: "1(2(4))(3)"
解释: 原本应该是 "1(2(4)())(3()())"，但你需要省略所有的空括号对。最终结果为 "1(2(4))(3)"。

示例 2:

输入: root = [1,2,3,null,4]
输出: "1(2()(4))(3)"
解释: 几乎与第一个示例相同，除了 2 后面的 () 是必要的，用来表示 2 缺少左子节点但有右子节点。

约束条件:

  • 树中节点的数量在 [1, 10^4] 范围内
  • -1000 <= Node.val <= 1000

解题思路

这道题要求按照特定规则将二叉树转换为字符串表示。核心思路是使用前序遍历（根-左-右）来构建字符串。

解题思路分析：

  1. 基本思路：对每个节点，先添加节点值，然后递归处理左右子树

  2. 关键规则理解：

    • 如果节点没有子节点：直接输出节点值，不加括号
    • 如果只有左子节点：输出 节点值(左子树)
    • 如果只有右子节点：输出 节点值()(右子树) （注意空括号不能省略）
    • 如果有左右子节点：输出 节点值(左子树)(右子树)

  3. 实现方式：使用递归的深度优先搜索

    • 对于每个节点，先将节点值加入结果
    • 判断是否需要添加括号：当节点有子节点时才需要
    • 递归处理左子树（如果存在）
    • 处理右子树时要特别注意：如果没有左子树但有右子树，需要添加空括号

  4. 边界情况处理：

    • 根节点为空（题目约束保证不会出现）
    • 叶子节点：直接返回节点值
    • 只有右子树的节点：必须保留左侧空括号

这种方法时间复杂度为O(n)，空间复杂度为O(h)，其中h是树的高度。

代码实现

class Solution {
public:
    string tree2str(TreeNode* root) {
        if (!root) return "";
        
        string result = to_string(root->val);
        
        // 如果有左子树，递归处理
        if (root->left) {
            result += "(" + tree2str(root->left) + ")";
        }
        // 如果没有左子树但有右子树，需要添加空括号
        else if (root->right) {
            result += "()";
        }
        
        // 如果有右子树，递归处理
        if (root->right) {
            result += "(" + tree2str(root->right) + ")";
        }
        
        return result;
    }
};

class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:
        if not root:
            return ""
        
        result = str(root.val)
        
        # 如果有左子树，递归处理
        if root.left:
            result += "(" + self.tree2str(root.left) + ")"
        # 如果没有左子树但有右子树，需要添加空括号
        elif root.right:
            result += "()"
        
        # 如果有右子树，递归处理
        if root.right:
            result += "(" + self.tree2str(root.right) + ")"
        
        return result

public class Solution {
    public string Tree2str(TreeNode root) {
        if (root == null) return "";
        
        string result = root.val.ToString();
        
        // 如果有左子树，递归处理
        if (root.left != null) {
            result += "(" + Tree2str(root.left) + ")";
        }
        // 如果没有左子树但有右子树，需要添加空括号
        else if (root.right != null) {
            result += "()";
        }
        
        // 如果有右子树，递归处理
        if (root.right != null) {
            result += "(" + Tree2str(root.right) + ")";
        }
        
        return result;
    }
}

var tree2str = function(root) {
    if (!root) return "";
    
    let result = root.val.toString();
    
    // 如果有左子树，递归处理
    if (root.left) {
        result += "(" + tree2str(root.left) + ")";
    }
    // 如果没有左子树但有右子树，需要添加空括号
    else if (root.right) {
        result += "()";
    }
    
    // 如果有右子树，递归处理
    if (root.right) {
        result += "(" + tree2str(root.right) + ")";
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是树中节点的数量，需要访问每个节点一次
空间复杂度O(h)，其中 h 是树的高度，递归调用栈的深度最多为树的高度

相关题目