LeetCode 题解工作台
根据二叉树创建字符串
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。 空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。 示例 1： 输入： root = [1,2,3,4] 输出： …
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
class Solution: def tree2str(self, root: Optional[TreeNode]) -> str:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1：
输入：root = [1,2,3,4] 输出："1(2(4))(3)" 解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
示例 2：
输入：root = [1,2,3,null,4] 输出："1(2()(4))(3)" 解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。
提示：
- 树中节点的数目范围是
[1, 104] -1000 <= Node.val <= 1000
解题思路
方法一
# 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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate correctly identifies the pattern of binary tree traversal and can apply recursion for string construction.
- question_mark
Candidate handles edge cases involving null children and correctly omits empty parentheses.
- question_mark
Candidate demonstrates awareness of efficient string construction to avoid performance bottlenecks.
常见陷阱
外企场景- error
Failing to handle null children correctly by not omitting empty parentheses or incorrectly representing them.
- error
Using inefficient string concatenation methods that could lead to performance issues in large trees.
- error
Not properly formatting the output string when there is a node with only one child.
进阶变体
外企场景- arrow_right_alt
Handle a binary tree that contains only left or right children, ensuring correct output formatting.
- arrow_right_alt
Optimize the approach for very large trees, considering both time and space efficiency.
- arrow_right_alt
Modify the problem to return the result in a different format, such as JSON or a list representation.