1028. Recover a Tree From Preorder Traversal (Hard) - TengnanYao/daily_leetcode GitHub Wiki

# 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 recoverFromPreorder(self, S):
        """
        :type S: str
        :rtype: TreeNode
        """
        dummy = TreeNode()
        stack = [(-1, dummy)]
        n = len(S)
        cur, count = "", 0
        i = 0
        while i < n:
            while i < n and S[i] == "-":
                count += 1
                i += 1
            while i < n and S[i] != "-":
                cur += S[i]
                i += 1
            node = TreeNode(cur)
            if count > stack[-1][0]:
                stack[-1][1].left = node
            else:
                for _ in range(stack[-1][0] - count + 1):
                    stack.pop()
                stack[-1][1].right = node
            stack.append((count, node))
            cur, count = "", 0
        return dummy.left