难度: Medium
给你二叉树的根节点 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运行时间: 30 ms
内存: 17.3 MB
# 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:
if not root:
return ''
if not root.left and not root.right:
return str(root.val)
if not root.right:
return str(root.val) + '(' + self.tree2str(root.left) + ')'
return str(root.val) + '(' + self.tree2str(root.left) + ')' + '(' + self.tree2str(root.right) + ')'
这个题解采用递归的方式，通过前序遍历二叉树来构造字符串。对于每个节点，先将节点的值转化为字符串，然后递归处理左子树和右子树。如果左子树为空而右子树不为空，需要保留左子树的空括号对。最后将左右子树的结果用括号括起来，与当前节点的值拼接。
时间复杂度: O(n)
空间复杂度: O(n)
# 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:
if not root:
return ''
# 如果是叶子节点，直接返回节点值
if not root.left and not root.right:
return str(root.val)
# 如果左子树为空而右子树不为空，需要保留左子树的空括号对
if not root.right:
return str(root.val) + '(' + self.tree2str(root.left) + ')'
# 递归处理左右子树，用括号括起来，与当前节点值拼接
return str(root.val) + '(' + self.tree2str(root.left) + ')' + '(' + self.tree2str(root.right) + ')'
当递归函数遇到空节点时返回空字符串而不是一对空括号，这样做可以避免在最终的字符串中出现不必要的空括号对。如果返回空括号对，那么对于任何没有子节点的节点都会生成一个额外的'()'，这会导致字符串不仅冗长，而且会误解树的实际结构。因此，返回空字符串可以确保只有在必要的情况下（即有右子树而无左子树时），才添加括号，从而保持输出的整洁和准确。
在生成树的字符串表示时，如果右子树非空而左子树为空，包括一个空的括号对是必要的，以避免歧义。这是因为按照题目要求的格式，若直接省略左子树的括号而只添加右子树的括号，解释器或读者可能会错误地将右子树的内容误认为是左子树的内容。因此，使用一个空的括号对来明确表示左子树为空，可以确保树的结构被正确理解。
对于叶子节点直接返回节点值是适当的处理方式，因为叶子节点没有左右子树，因此不需要添加任何括号。这种处理方式不仅简化了代码逻辑，还有助于保持生成的字符串的简洁性。对于更复杂的树结构，该方法依然能够正确描述树的结构，因为对于非叶子节点，其左右子树（无论是否为空）都会在递归过程中被适当地处理并加上必要的括号，从而确保整个树的结构在字符串中被正确反映。