606.-construct-string-from-binary-tree.md

606. Construct String from Binary Tree

• Easy
• Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.
• Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
• https://leetcode.com/problems/construct-string-from-binary-tree/

Solution 1

Runtime: 52 msMemory Usage: 16 MB

class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:
        if not root:
            return ''
        result=str(root.val)
        if root.left:
            result+='('+self.tree2str(root.left)+')'
            if root.right:
                result+='('+self.tree2str(root.right)+')'
        elif root.right:
            result+='()'+'('+self.tree2str(root.right)+')'
        return result

{% hint style="info" %} Simple recursive method. Added two layers of 'if' to focus on the case of having a right subtree but not a left subtree. {% endhint %}

Solution 2

Runtime: 56 msMemory Usage: 15.4 MB

class Solution(object):
    def tree2str(self,t):
        if not t: return ""
        stack = []
        stack.append(t)
        res = ""
        while stack:
            node = stack.pop()
            if node == ")":
                res += ")"
                continue
            res += "("+str(node.val)
            if not node.left and  node.right:
                res += "()"
            if  node.right:
                stack.append(")")
                stack.append(node.right)
            if  node.left:
                stack.append(")")
                stack.append(node.left)

        return res[1:]

{% hint style="info" %} Iterative method. Returning from the second place is to remove the unnecssary '(' at the first. {% endhint %}