[LeetCode]606. Construct String

题目

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     
Output: "1(2(4))(3)"
Explanation: Originallay it needs to be "1(2(4)())(3()())", 
but you need to omit all the unnecessary empty parenthesis pairs. 
And it will be "1(2(4))(3)".

Example 2:

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example, 
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

难度

Easy

方法

用递归的方法前序遍历，在遍历节点前加入(，遍历节点后加入)即可。如果左右子节点为空，则不需要其子节点的()。如果只有右子节点，则左子节点需要用()代替，以区分只有左子节点而无右子节点的情况

python代码

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def __init__(self):
        self.result = ""

    def tree2str(self, t):
        """
        :type t: TreeNode
        :rtype: str
        """
        if t:
            self.result += str(t.val)
            if t.left or t.right:
                self.result += "("
            self.tree2str(t.left)
            if t.left or t.right:
                self.result += ")"
            if t.right:
                self.result += "("
                self.tree2str(t.right)
                self.result += ")"
        
        return self.result

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)

assert Solution().tree2str(root) == "1(2(4))(3)"