0606：根据二叉树创建字符串（★）

2016-08-28 约 422 字预计阅读 1 分钟次阅读

力扣第 606 题

题目

给你二叉树的根节点 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, 10⁴]
-1000 <= Node.val <= 1000

相似问题：

分析

分情况递归，根据左右子树是否为空判断是否省略括号
假如右子树非空，左子树不能省略括号
假如右子树为空，可以省略左右子树的括号

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:
        def dfs(u):
            if not u:
                return ''
            if not u.left and not u.right:
                return str(u.val)
            if not u.right:
                return '%d(%s)'%(u.val,dfs(u.left))
            return '%d(%s)(%s)'%(u.val,dfs(u.left),dfs(u.right))
        return dfs(root)

43 ms

目录

0606：根据二叉树创建字符串（★）

题目

分析

解答