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

Categories:

题目描述
思路分析
1. 解法一：递归（DFS）（推荐）
2. 解法二：迭代（栈 + DFS）
相似题目

题目描述

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

思路分析

解法一：递归（DFS）（推荐）

核心思路：

对二叉树进行前序遍历（根 → 左 → 右），递归构建字符串

规则：若左子树为空且右子树不为空，左侧需保留空括号 ()；若右子树为空，则省略右括号

递归终止条件：节点为 null 时返回空字符串

复杂度分析：

时间复杂度：O(n)，其中 n 表示二叉树的节点数，每个节点访问一次

空间复杂度：O(n)，递归栈深度最坏为 O(n)，字符串拼接结果也为 O(n)

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.left == null) {
            return root.val + "()" + "(" + tree2str(root.right) + ")";
        }

        // 无右子树，省略右括号
        if (root.right == null) {
            return root.val + "(" + tree2str(root.left) + ")";
        }

        // 左右子树都存在
        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.Left == nil {
        return strconv.Itoa(root.Val) + "()" + "(" + tree2str(root.Right) + ")"
    }

    // 无右子树，省略右括号
    if root.Right == nil {
        return strconv.Itoa(root.Val) + "(" + tree2str(root.Left) + ")"
    }

    // 左右子树都存在
    return strconv.Itoa(root.Val) + "(" + tree2str(root.Left) + ")" + "(" + tree2str(root.Right) + ")"
}

解法二：迭代（栈 + DFS）

核心思路：

使用显式栈模拟递归过程，配合 StringBuilder 拼接字符串

用 Set 记录已处理过的节点，区分首次访问（压入左右子节点）与回溯（追加 )）

复杂度分析：

时间复杂度：O(n)，其中 n 表示二叉树的节点数

空间复杂度：O(n)，栈和 Set 最多存储 O(n) 个节点

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> stack = new ArrayDeque<>();
        Set<TreeNode> visited = new HashSet<>();

        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();

            if (visited.contains(node)) {
                // 回溯时追加右括号
                stack.pop();
                sb.append(")");
            } else {
                visited.add(node);
                sb.append("(").append(node.val);

                // 先压右子节点，再压左子节点（保证左子先处理）
                if (node.left == null && node.right != null) {
                    sb.append("()");
                }
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }

        // 去掉最外层括号
        return sb.substring(1, sb.length() - 1);
    }
}

func tree2str(root *TreeNode) string {
    var sb strings.Builder
    stack := []*TreeNode{}
    visited := map[*TreeNode]bool{}

    stack = append(stack, root)

    for len(stack) > 0 {
        node := stack[len(stack)-1]

        if visited[node] {
            // 回溯时追加右括号
            stack = stack[:len(stack)-1]
            sb.WriteByte(')')
        } else {
            visited[node] = true
            sb.WriteByte('(')
            sb.WriteString(strconv.Itoa(node.Val))

            // 左子树为空但右子树不为空，补空括号
            if node.Left == nil && node.Right != nil {
                sb.WriteString("()")
            }
            if node.Right != nil {
                stack = append(stack, node.Right)
            }
            if node.Left != nil {
                stack = append(stack, node.Left)
            }
        }
    }

    // 去掉最外层括号
    result := sb.String()
    return result[1 : len(result)-1]
}

相似题目

题目	难度	考察点
94. 二叉树的中序遍历	简单	二叉树、DFS
144. 二叉树的前序遍历	简单	二叉树、DFS
297. 二叉树的序列化与反序列化	困难	二叉树、字符串
331. 验证二叉树的前序序列化	中等	二叉树、字符串
536. 从字符串生成二叉树	中等	二叉树、字符串、递归
652. 寻找重复的子树	中等	二叉树、哈希表

本文作者: HGNULB

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