题目描述
思路解析动画文字版
记住三句话:值在前、左子树必带括号、右子树有才带。空括号只在「左空右非空」时保留,下面每帧都在套它。
准备 · 前序遍历：开局答案串为空。我们从根节点 50 开始,按前序遍历:先写当前节点,再写左子树、右子树。盯住右侧的「已生成串」,它会一个字符一个字符地长出来。
进入 · 写 50：走到节点 50(紫色),前序遍历第一步就是把它的值写进串,现在串是 50。
判定 50 的孩子：50 左右孩子都在,接下来要写「(左子树)(右子树)」两组括号。
50 · 左括号：给 50 写下左括号,准备把它的左子树装进去。串变成 50(。
进入 · 写 30：走到节点 30(紫色),前序遍历第一步就是把它的值写进串,现在串是 50(30。
判定 30 的孩子：30 左孩子空、但右孩子 60 在,这就是关键边界:左边要保留一对空括号 "()" 占位。
30 · 左括号：给 30 写下左括号,准备把它的左子树装进去。串变成 50(30(。
30 · 空左括号 ()：30 左孩子是空的,但因为右孩子还在,这对括号不能省。写成空的 "()" 占住左孩子的位置,否则右子树会被误读成左孩子。串变成 50(30()。
30 · 右子树开括号：给 30 写下右子树的开括号 (,进入它的右子树。串变成 50(30()(。
进入 · 写 60：走到节点 60(紫色),前序遍历第一步就是把它的值写进串,现在串是 50(30()(60。
叶子 60：60 左右都没有孩子,是叶子。叶子后面什么括号都不写,直接它的值就完事,标绿表示已处理。
30 · 闭合右括号：30 的右子树写完,补上闭合的右括号。现在串是 50(30()(60)。
收尾 30：30 的左右子树全部写完,它对应的片段就是 30()(60),标绿收工。
50 · 闭合左括号：50 的左子树写完了,补上闭合的右括号,左半部分收口。现在串是 50(30()(60))。
50 · 右子树开括号：给 50 写下右子树的开括号 (,进入它的右子树。串变成 50(30()(60))(。
进入 · 写 80：走到节点 80(紫色),前序遍历第一步就是把它的值写进串,现在串是 50(30()(60))(80。
判定 80 的孩子：80 只有左孩子、右孩子是空的,左括号要写,右边那组括号可以省略。
80 · 左括号：给 80 写下左括号,准备把它的左子树装进去。串变成 50(30()(60))(80(。
进入 · 写 70：走到节点 70(紫色),前序遍历第一步就是把它的值写进串,现在串是 50(30()(60))(80(70。
叶子 70：70 左右都没有孩子,是叶子。叶子后面什么括号都不写,直接它的值就完事,标绿表示已处理。
80 · 闭合左括号：80 的左子树写完了,补上闭合的右括号,左半部分收口。现在串是 50(30()(60))(80(70)。
80 · 右子树括号整组省略：80 右孩子是空的,而且省掉不会破坏一一映射,所以右边那对括号整组省略,一个字符都不写。
收尾 80：80 的左右子树全部写完,它对应的片段就是 80(70),标绿收工。
50 · 闭合右括号：50 的右子树写完,补上闭合的右括号。现在串是 50(30()(60))(80(70))。
收尾 50：50 的左右子树全部写完,它对应的片段就是 50(30()(60))(80(70)),标绿收工。
完成 · 答案：整棵树前序走完,最终答案是 50(30()(60))(80(70))。回看两处省略:30 的左孩子空但右孩子在,保留了 "()";80 只有左孩子,右子树那组括号被整组省掉。这正是题目省略规则的精髓。
三个边界把规则两端都覆盖:单节点、左空右非空(留括号)、只有左孩子(省右子树括号)。
面试就盯这一处不对称:左空要留、右空要省,本质都是为了保住一一映射。
参考代码
from __future__ import annotationsfrom 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 = rightclass 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 = rightclass 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)复杂度
- 时间：O(n)~O(n²)，遍历每个节点是 O(n);但本题参考解是「递归返回整段字符串直接拼接」(Python f-string / C++ string + / Java +),链状树上最坏会退化到 O(n²);要稳定 O(n) 需用 StringBuilder / list buffer 等可变缓冲追加
- 空间：O(h)，递归栈深度等于树高 h,最坏(链状树)O(n);不计输出串
易错点
面试追问把动画讲成自己的话
追问为什么「左空右非空」那对空括号不能省?
追问为什么「右孩子空」反而能省右子树括号?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
在二叉树中增加一行
LeetCode 623 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题