Recover a Tree From Preorder Traversal

Problem Id: 1028 Difficulty: Hard Tag: Tree Tag: Depth-first Search


Intuition

In general preorder traversal, there is no return value. In this problem, since we need to recover the tree, we use a return value TreeNode to construct the tree.

Solution


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


class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        preorder = []
        depth = 0
        value = ''
        for c in S + '\0':
            if c in string.digits:
                value += c
            elif value:
                preorder.append([int(value), depth])
                value = ''
                depth = 1
            else:
                depth += 1

        self.index = 0
        self.preorder = preorder
        return self._helper(0)

    def _helper(self, depth):
        if self.index < len(self.preorder) and \
                self.preorder[self.index][1] == depth:
            node = TreeNode(self.preorder[self.index][0])
            self.index += 1
            node.left = self._helper(depth + 1)
            node.right = self._helper(depth + 1)
            return node
        return None