[LeetCode] 606 | Construct String form Binary Tree | Python

---

문제 링크: https://leetcode.com/problems/construct-string-from-binary-tree/

---

문제

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.

---

조건

• The number of nodes in the tree is in the range [1, $10^4$].
• -1000 <= Node.val <= 1000

---

내 풀이

Tree 관련 문제는 dfs를 활용해 recursive하게 짠다.

이 문제와 같은 경우는 root.left와 root.right에 값이 있을 때와 없을 때 구분해서 리턴해주면 된다.

---

코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:
        def traverse(root):
            if not root:
                return
            
            left = traverse(root.left)
            right = traverse(root.right)
            
            if not left and not right:
                return str(root.val)
            elif not right:
                return str(root.val) + '(' + left + ')'
            elif not left:
                return str(root.val) + '()(' + right + ')'
            else:
                return str(root.val) + '(' + left + ')' + '(' + right + ')'
        
        return traverse(root)