教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇技术指南围绕「LeetCode 0606. 根据二叉树创建字符串」展开讲解如何通过前序遍历Preorder Traversal配合深度优先搜索DFS把一棵二叉树转换成一个由括号和整数组成的字符串并重点剖析「何时必须保留空括号()、何时可以省略」这一核心规则。读完本文你将掌握该题的四条括号构造规则、可直接运行的 Python 递归解法、递归调用链的逐步推演以及时间/空间复杂度分析该题也是 二叉树遍历 与 字符串处理 两类基础能力的综合应用。1. 题目概览1.1 题目链接与基础信息题目编号0606. 根据二叉树创建字符串Construct String from Binary Tree标签树、深度优先搜索、字符串、二叉树难度中等题解原文docs/solutions/0600-0699/construct-string-from-binary-tree.md1.2 题目大意给定二叉树的根节点root要求采用前序遍历的方式将二叉树转化为一个由括号和整数组成的字符串并返回构造出的字符串。其中空节点使用一对空括号对()表示转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。1.3 数据范围约束树中节点的数目范围是 $[1, 10^{4}]$节点取值满足 $-10^{3} \le Node.val \le 10^{3}$。节点规模最多可达 $10^4$意味着任何 $O(n^2)$ 级别以上的实现都可能超时只有线性级别的遍历方案是安全的同时节点值为负数时需要正确处理负号与括号的位置关系。2. 示例逐层拆解2.1 示例 1右子树为空时省略括号输入root [1,2,3,4] 输出1(2(4))(3)解释若不做任何省略初步转化会得到1(2(4)())(3()())即每个左/右子位置都用括号对补齐。但观察节点2它有左孩子4、右孩子为空此时右孩子位置的空括号对()并不影响字符串与二叉树的一一对应可以省略节点3左右孩子均为空它的()()同样可以完全省略。最终字符串为1(2(4))(3)。2.2 示例 2左子树为空时不能省略输入root [1,2,3,null,4] 输出1(2()(4))(3)解释节点2没有左孩子、但有右孩子4。此时左孩子位置的空括号对()不能省略——一旦省略字符串会变成1(2(4))(3)与示例 1 的输出完全相同就无法区分「4是2的左孩子」还是「4是2的右孩子」从而破坏字符串与二叉树的一对一映射关系。3. 核心解题思路前序遍历 DFS3.1 为什么用前序遍历前序遍历的顺序是「根节点 → 左子树 → 右子树」详见 二叉树前序遍历。本题要求「采用前序遍历的方式」构造字符串因此递归时总是先输出当前节点值再递归处理左子树、右子树这与标准的二叉树前序遍历递归框架完全一致def preorder(node): if not node: return # 1. 访问根节点 # 2. 递归遍历左子树 # 3. 递归遍历右子树本题只是在「访问根节点」后将左右子树的递归结果用括号包裹并拼接成字符串。3.2 括号省略的完整规则题解 construct-string-from-binary-tree.md 总结出四条规则它们是本题的唯一难点务必牢记节点情况括号处理说明节点有左子树在左子树的字符串外加上括号左孩子位置始终用(左子树串)包裹节点有右子树在右子树的字符串外加上括号右孩子位置用(右子树串)包裹节点没有左子树但有右子树在左子树位置补上空括号()必须保留否则映射关系被破坏节点既没有左子树也没有右子树不加任何括号直接返回节点值字符串等价地概括只要存在右子树就必须先输出左位置的括号对左子树为空时输出()只要存在左子树右位置为空时可以省略右括号对。3.3 为什么左空右非空时必须补()从字符串的形态上可以直观验证1(2(4))(3)中4被解析为2的左孩子1(2()(4))(3)中()占据左孩子槽位4被解析为2的右孩子。正是这个「占位空括号」保留了孩子位置的语义保证了双向唯一的映射给定二叉树可唯一生成字符串给定字符串也能唯一还原二叉树这正是 LeetCode 上「根据二叉树创建字符串」与 0652. 寻找重复的子树 等序列化类题目共同依赖的性质。4. 完整可运行代码以下为题解原文提供的 Python 实现基于TreeNode定义Optional来自typing# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def tree2str(self, root: Optional[TreeNode]) - str: if not root: return # 只有根节点 if not root.left and not root.right: return str(root.val) # 有左子树没有右子树 if root.left and not root.right: return str(root.val) ( self.tree2str(root.left) ) # 有右子树无论是否有左子树 return str(root.val) ( self.tree2str(root.left) )( self.tree2str(root.right) )4.1 代码与规则的一一对应代码分支覆盖的规则if not root: return 递归基空节点返回空串仅在越界访问时触发if not root.left and not root.right: return str(root.val)叶子节点不加括号if root.left and not root.right:有左无右只包左子树括号省略右括号末尾的return分支有右子树左位置无论是否为空都用括号包裹self.tree2str(root.left)对空左子树返回恰好形成()右子树正常包裹注意最后一个分支的精妙之处当左子树为空时self.tree2str(root.left)返回拼接后得到str(root.val) () ( 右子树串 )空括号()被自动生成无需显式特判这正是示例 2 中1(2()(4))(3)的由来。4.2 递归调用链逐步推演示例 1以root [1,2,3,4]为例tree2str(1)有左孩子2、右孩子3进入末尾分支 →1 ( tree2str(2) ) ( tree2str(3) )tree2str(2)有左孩子4、无右孩子进入第二分支 →2 ( tree2str(4) )tree2str(4)叶子节点 →4tree2str(3)叶子节点 →3。自底向上回代得到1 (2(4)) (3) 1(2(4))(3)与预期输出一致。5. 复杂度分析时间复杂度$O(n)$其中 $n$ 是二叉树的节点数。递归过程中每个节点被访问且仅被访问一次每次访问只做常数次字符串拼接与判断。空间复杂度$O(n)$。递归调用栈的深度在最坏情况下退化为链状的单支树可达 $n$同时每次拼接都会产生新的中间字符串累计的临时字符串开销也为 $O(n)$。作为对照二叉树遍历 中给出的标准前序遍历时间复杂度同为 $O(n)$、空间复杂度为 $O(h)$$h$ 为树高最坏 $O(n)$本题与其一致说明该解法在 $10^4$ 节点规模下是安全且最优的。6. 易错点与边界情况小结负数节点值如-10str(root.val)得到-10拼接规则不变括号始终包裹在子树字符串外层不会出现歧义单节点树root [1]输出1走叶子分支不加任何括号只有左链的树root [1,2,null,3]输出1(2(3))每一层都省略右侧空括号只有右链的树root [1,null,2,null,3]输出1()(2()(3))每一层都必须保留左侧()占位——这是最容易写错的场景空左补()是区分左右孩子的唯一手段删掉它会直接导致字符串与二叉树失去一对一映射违背题意。7. 进一步延伸本题属于「二叉树的序列化」家族掌握括号省略规则后可进一步阅读仓库中相关题解加深理解0652. 寻找重复的子树需要为每棵子树生成规范化字符串本质是同一套序列化思维的运用0654. 最大二叉树 与 0655. 输出二叉树从数组/二叉树反方向的构造与可视化可与本题互为对照若希望系统复习前序遍历的递归与非递归显式栈两种写法可回到 二叉树遍历 章节其「先右后左入栈」的迭代框架同样可以改造成本题的迭代解法题目索引可参考 0600-0699 题解索引 与 题解总列表。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐从字符串构造二叉树LeetCode 536 括号编码串的递归解析与实现详解AlgoNote 算法通关手册从字符串构造二叉树LeetCode 536 括号编码串的递归解析与实现详解AlgoNote 算法通关手册 导读 本文围绕 0536. 从字符串生成二叉树教程文档知识库LeetCode 0257「二叉树的所有路径」解题指南DFS 遍历与路径拼接AlgoNote 算法通关手册LeetCode 0257「二叉树的所有路径」解题指南DFS 遍历与路径拼接AlgoNote 算法通关手册 本篇基于 AlgoNote 算法通关手册的题解教程文档知识库「算法通关手册」LeetCode 0545二叉树的边界——分治 DFS 求解二叉树逆时针边界遍历「算法通关手册」LeetCode 0545二叉树的边界——分治 DFS 求解二叉树逆时针边界遍历 本篇题解基于「算法通关手册」题解库 docs/solut教程文档知识库上一篇ESPnet2 OWSM v3.1 多语言语音识别实战E-Branchformer 编码器选型、训练配置与数据准备全流程下一篇IPTVnator Xtream Code支持专业IPTV服务集成创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考