根据二叉树创建字符串 图解题解

要把二叉树变成什么样的字符串

给一棵二叉树的根 root，按前序遍历，也就是先写自己再写左右子树，压成一行字符串：节点值在前，左右子树各用一对括号包住。省掉某对空括号后字符串还能唯一还原回这棵树，就省掉它。题面 root=[1,2,3,4] 拼成 "1(2(4))(3)"，另一个只挪一个孩子，差别全在左孩子在不在。

括号全写满，串里会多出哪些空壳

一个偷懒的拼法是每个节点都写成 值(左子树)(右子树)。这样叶子 4 会拼成 "4()()"、只有左孩子的节点右边也拖一对 ()，满树都是空气括号。可题目要省掉所有不影响还原的空括号，写满的留不住。

右孩子空能省、左孩子空却不能，差在哪

省括号的底线是省完后字符串还能唯一读回原来那棵树。右孩子为空时那对括号能省：左孩子已写在前面、位置定死，后面不再冒括号就代表右边没东西，只有左孩子的节点写成 值(左) 就够。但左孩子空、右孩子还在时那对空 () 必须留：省成 值(右)，读串时会把里头第一段当成左孩子，右孩子被顶到左孩子的位置、成了另一棵树；留一对空 () 占位，后面那对 (右) 才认成右孩子。

递归到一个节点，该返回哪一段串

把拼串写成递归函数，每到一个节点只返回它这一小段。空节点返回空串；叶子，也就是左右孩子都没有，直接返回值、不添括号；右孩子空、左孩子在的节点返回 值(左)，右边不写；右孩子在时不管左孩子，都返回 值(左)(右)——左孩子若空，左段是空串，拼出来正好是 值()(右)，那对必须留的空 () 就这么冒出来。判完这四种，根返回的那段就是答案。

两棵四节点的树，分别拼成什么

先看 root=[1,2,3,4]：1 左孩子 2、右孩子 3，2 左孩子 4。1 左右都在，拼 值(左)(右)。到 2，右孩子空、左孩子 4 在，返回 值(左)，4 是叶子返回 "4"，2 这段是 "2(4)"；3 是叶子返回 "3"。1 拼成 "1(2(4))(3)"，跟题面输出一致。

再看 root=[1,2,3,null,4]，2 的左孩子挪空、右孩子换成 4。到 2 时左孩子空、右孩子 4 在，落进最后一种，返回 值(左)(右)：左边空串、右边 4 返回 "4"，拼成 "2()(4)"，中间那对空 () 正占住空左孩子的位置。1 和 3 不变，最终 "1(2()(4))(3)"，差别只在 2 这段那对空括号留没留。

拼串会不会拖慢，哪三种树最该拿去试

遍历每个节点一次是 O(n)。但参考解法递归返回一整段字符串再往上拼，像 Python 的 f-string、C++/Java 的字符串相加，每拼一次都要复制下层整段；链状的树上越靠上复制的串越长，累计最坏滑到 O(n²)。想稳在 O(n)，改用 StringBuilder 往末尾追加、不反复复制即可。空间是递归栈深度 O(h)，链状树最坏 O(n)。

拿三种树戳：单节点的树只该吐一个值、别拖括号；左孩子空、右孩子在的树，那对空 () 得原样还在，省了右子树就会被当成左孩子；只有左孩子的树，右边整组括号得省掉，多一对就不是最简。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:
        def dfs(root):
            if root is None:
                return ''
            if root.left is None and root.right is None:
                return str(root.val)
            if root.right is None:
                return f'{root.val}({dfs(root.left)})'
            return f'{root.val}({dfs(root.left)})({dfs(root.right)})'

        return dfs(root)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* root) {
        if (!root) return "";
        if (!root->left && !root->right) return to_string(root->val);
        if (!root->right) return to_string(root->val) + "(" + tree2str(root->left) + ")";
        return to_string(root->val) + "(" + tree2str(root->left) + ")(" + tree2str(root->right) + ")";
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public String tree2str(TreeNode root) {
        if (root == null) {
            return "";
        }
        if (root.left == null && root.right == null) {
            return root.val + "";
        }
        if (root.right == null) {
            return root.val + "(" + tree2str(root.left) + ")";
        }
        return root.val + "(" + tree2str(root.left) + ")(" + tree2str(root.right) + ")";
    }
}