construct_string_binary_tree.py (1795B)
| # 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)"
|
