aboutsummaryrefslogtreecommitdiff
path: root/construct_string_binary_tree.py
blob: 012b56907d10b6740547f07deea486f04be03f0d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# 606. 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
"""


# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def tree2str(self, root):
        """
        :type root: TreeNode
        :rtype: str
        """

        def generate_paren_str(self, node):
            if not node:
                return ""

            left_str = generate_paren_str(node.left)
            right_str = generate_paren_str(node.right)
            level_str = f"{node.val}({left_str})({right_str})"
            return level_str

        def strip_excessive_parenthesis(self, parenthesis_str):
            final_str = []
            n = len(parenthesis_str)
            i = 0
            while i < n:
                if i + 4 <= n and parenthesis_str[i : i + 4] == "()()":
                    i += 4
                    continue

                if i + 3 <= n and (
                    parenthesis_str[i : i + 3] == "())"
                    or parenthesis_str[i : i + 3] == ")()"
                ):
                    i += 2
                    continue

                final_str.append(parenthesis_str[i])
                i += 1
            return "".join(final_str)

        return strip_excessive_parenthesis(generate_paren_str(root))


if __name__ == "__main__":
    obj = Solution()
    print(obj.tree2str(root=[1, 2, 3, 4]))  # expect: "1(2(4))(3)"