LeetCode 606中等树 · BST
根据二叉树创建字符串 图解题解
这道题到底在问什么
给二叉树根 root,前序遍历转成字符串:节点值在前,左右子树各用一对括号包住。省略所有不影响「字符串与树一一映射」的空括号。约束:节点数 1 ≤ n ≤ 10000,节点值 -1000 ≤ val ≤ 1000。
- 输入
- root=[1,2,3,4]
- 输出
- "1(2(4))(3)"
- 输入
- root=[1,2,3,null,4]
- 输出
- "1(2()(4))(3)"
最优解：一步一步想明白
- 3记住三句话:值在前、左子树必带括号、右子树有才带。空括号只在「左空右非空」时保留,下面每帧都在套它。
- 4答案串为空开局答案串为空。我们从根节点 50 开始,按前序遍历:先写当前节点,再写左子树、右子树。盯住右侧的「已生成串」,它会一个字符一个字符地长出来。
- 5写下 50走到节点 50(紫色),前序遍历第一步就是把它的值写进串,现在串是 50。
- 6分析 50 左右50 左右孩子都在,接下来要写「(左子树)(右子树)」两组括号。
- 7写下 (给 50 写下左括号,准备把它的左子树装进去。串变成 50(。
- 8写下 30走到节点 30(紫色),前序遍历第一步就是把它的值写进串,现在串是 50(30。
- 9分析 30 左右30 左孩子空、但右孩子 60 在,这就是关键边界:左边要保留一对空括号 "()" 占位。
- 10写下 (给 30 写下左括号,准备把它的左子树装进去。串变成 50(30(。
- 11保留 ()30 左孩子是空的,但因为右孩子还在,这对括号不能省。写成空的 "()" 占住左孩子的位置,否则右子树会被误读成左孩子。串变成 50(30()。
- 12写下 (给 30 写下右子树的开括号 (,进入它的右子树。串变成 50(30()(。
- 13写下 60走到节点 60(紫色),前序遍历第一步就是把它的值写进串,现在串是 50(30()(60。
- 1460 是叶子60 左右都没有孩子,是叶子。叶子后面什么括号都不写,直接它的值就完事,标绿表示已处理。
- 15写下 )30 的右子树写完,补上闭合的右括号。现在串是 50(30()(60)。
- 1630 片段完成30 的左右子树全部写完,它对应的片段就是 30()(60),标绿收工。
- 17写下 )50 的左子树写完了,补上闭合的右括号,左半部分收口。现在串是 50(30()(60))。
- 18写下 (给 50 写下右子树的开括号 (,进入它的右子树。串变成 50(30()(60))(。
- 19写下 80走到节点 80(紫色),前序遍历第一步就是把它的值写进串,现在串是 50(30()(60))(80。
- 20分析 80 左右80 只有左孩子、右孩子是空的,左括号要写,右边那组括号可以省略。
- 21写下 (给 80 写下左括号,准备把它的左子树装进去。串变成 50(30()(60))(80(。
- 22写下 70走到节点 70(紫色),前序遍历第一步就是把它的值写进串,现在串是 50(30()(60))(80(70。
- 2370 是叶子70 左右都没有孩子,是叶子。叶子后面什么括号都不写,直接它的值就完事,标绿表示已处理。
- 24写下 )80 的左子树写完了,补上闭合的右括号,左半部分收口。现在串是 50(30()(60))(80(70)。
- 25右子树括号整组省略80 右孩子是空的,而且省掉不会破坏一一映射,所以右边那对括号整组省略,一个字符都不写。
- 2680 片段完成80 的左右子树全部写完,它对应的片段就是 80(70),标绿收工。
- 27写下 )50 的右子树写完,补上闭合的右括号。现在串是 50(30()(60))(80(70))。
- 2850 片段完成50 的左右子树全部写完,它对应的片段就是 50(30()(60))(80(70)),标绿收工。
- 29答案 = 50(30()(60))(80(70))整棵树前序走完,最终答案是 50(30()(60))(80(70))。回看两处省略:30 的左孩子空但右孩子在,保留了 "()";80 只有左孩子,右子树那组括号被整组省掉。这正是题目省略规则的精髓。
⚠️ 容易写错的地方
✗ 错：左空右非空时也省掉空括号
✓ 对：必须保留 "()" 占位
省了会让右子树被读成左孩子,破坏一一映射
✗ 错：给每个节点都写满两对括号
✓ 对：右孩子空时整组省略
题目要省略所有不影响映射的空括号,留着就不是最简形式
✗ 错：叶子后面还写一对 "()"
✓ 对：叶子只写值
叶子没孩子,任何括号都多余
完整代码（Python / C++ / Java）
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) + ")";
}
}复杂度
时间
O(n)~O(n²)
遍历每个节点是 O(n);但本题参考解是「递归返回整段字符串直接拼接」(Python f-string / C++ string + / Java +),链状树上最坏会退化到 O(n²);要稳定 O(n) 需用 StringBuilder / list buffer 等可变缓冲追加
空间
O(h)
递归栈深度等于树高 h,最坏(链状树)O(n);不计输出串
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 根据二叉树创建字符串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么「左空右非空」那对空括号不能省?+
因为字符串要和树一一映射。如果写成 "val(right)",解析时会把括号里的 right 当成 val 的左孩子,位置就错了。保留 "()" 占住左孩子的槽位,后面的 "(right)" 才会被正确读成右孩子。
为什么「右孩子空」反而能省右子树括号?+
左孩子已经写在前面、位置确定了,后面不再出现括号就意味着没有右孩子,不会产生歧义。题目明确要求省略所有不影响一一映射的空括号对,所以这组要省。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 根据二叉树创建字符串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。