LeetCode：606. Construct String from Binary Tree(构建一棵二叉树)

﹏ヽ暗。殇╰゛Y 2022-04-15 02:43 143阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

java实现方法1：

python实现方法1：

源码地址：

--------------------

### 题目描述： ###

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例 1:

输入: 二叉树: [1,2,3,4]
           1
         /   \
        2     3
       /    
      4     
    
    输出: "1(2(4))(3)"
    解释: 原本将是“1(2(4)())(3())”，在你省略所有不必要的空括号对之后，它将是“1(2(4))(3)”。

示例 2:

输入: 二叉树: [1,2,3,null,4]
           1
         /   \
        2     3
         \  
          4 
    
    输出: "1(2()(4))(3)"

解释: 和第一个示例相似，  
除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。

--------------------

### java实现方法1： ###

/**
         * 二叉树转成字符串
         *
         * @param t 二叉树
         * @return 字符串
         */
        public String tree2str(TreeNode t) {
            if (t == null){
                return "";
            }
            String left = tree2str(t.left);
            String right = tree2str(t.right);
            left = left.isEmpty() && right.isEmpty() ? "" : "(" + left + ")";
            right = right.isEmpty() ? "" : "(" + right + ")";
            return t.val + left + right;
        }

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### python实现方法1： ###

def tree_2_str(self, root: TreeNode) -> str:
            '''
                将树转成字符串
            Args:
                root: 二叉树
            Returns:
                字符串str
            '''
            if root == None:
                return ''
            left = str(self.tree_2_str(root.left))
            right = str(self.tree_2_str(root.right))
            left = '' if len(left) < 1 and len(right) < 1 else '(' + str(left) + ')'
            right = '' if len(right) < 1 else '(' + str(right) + ')'
            return str(root.val) + left + right

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### 源码地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode