Leetcode 1093 Solution

This article provides solution to leetcode question 1093 (recover-a-tree-from-preorder-traversal)
Categories:
Tags:
Access this page by simply typing in "lcs 1093" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/recover-a-tree-from-preorder-traversal

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 recoverFromPreorder(self, S: str) -> TreeNode:
        a = []
        i = 0
        while i < len(S):
            j = i
            while S[j] == '-':
                j += 1



            k = j
            while k < len(S) and S[k] != '-':
                k += 1



            a.append((j - i, int(S[j:k])))
            i = k



        self.i = 0
        def dfs(a, depth):
            if self.i == len(a):
                return None



            if a[self.i][0] != depth:
                return None



            node = TreeNode(a[self.i][1])
            self.i += 1
            node.left = dfs(a, depth + 1)
            node.right = dfs(a, depth + 1)
            return node



        return dfs(a, 0)