Construct String from Binary Tree

Problem Id: 606 Difficulty: Easy Tag: String Tag: Tree


Intuition

This string is the inorder of the tree with some additional parenthesis.

Solution


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

class Solution:
    def tree2str(self, t: TreeNode) -> str:
        self.order = ''
        self._dfs(t)
        return self.order

    def _dfs(self, node):
        if node is None:
            return
        self.order += str(node.val)

        if node.left:
            self.order += '('
            self._dfs(node.left)
            self.order += ')'
        elif node.right is not None:
            self.order += '()'

        if node.right:
            self.order += '('
            self._dfs(node.right)
            self.order += ')'