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

Posted on | In
Words count in article: 328 | Reading time ≈ 1

题目

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

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

示例1:

1
2
3
输入：root = [1,2,3,4]
输出："1(2(4))(3)"
解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)"

示例2：

1
2
3
输入：root = [1,2,3,null,4]
输出："1(2()(4))(3)"
解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。

提示：

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

解法

解法一：

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        travel(root, sb);
        return sb.toString();
    }

    private void travel(TreeNode root, StringBuilder sb) {
        if (Objects.isNull(root)) {
            return;
        }

        sb.append(root.val);
        if (!Objects.isNull(root.left) || !Objects.isNull(root.right)) {
            sb.append('(');
            travel(root.left, sb);
            sb.append(')');
            if (root.right != null) {
                sb.append('(');
                travel(root.right, sb);
                sb.append(')');
            }
        }
    }
0%