Leetcode 0606 Construct String from Binary Tree

Problem statement

https://leetcode.com/problems/construct-string-from-binary-tree/

Solution

Note, that if we have left children and do not have right, than we do not need additional empty brackets. If we have right children we need to call function recursively for both children: and if one of them (left) is empty, then empty brackets will be created automatically.

Complexity

Time complexity is O(n), space complexity is O(h), where h is height of tree.

Code

class Solution:
    def tree2str(self, root):
        if not root: return ""
        s = str(root.val)
        if not root.left and not root.right:
            return s
        if root.left and not root.right:
            return s + "(" + self.tree2str(root.left) + ")"
        return s + "(" + self.tree2str(root.left) + ")(" + self.tree2str(root.right) + ")"