Recover a Tree From Preorder Traversal — LeetCode 1028 Python Solution

from typing import Optional

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

def recoverFromPreorder(traversal: str) -> Optional[TreeNode]:
    i = 0
    stack = []  # (node, depth)
    while i < len(traversal):
        depth = 0
        while i < len(traversal) and traversal[i] == '-':
            depth += 1
            i += 1
        val = 0
        while i < len(traversal) and traversal[i].isdigit():
            val = val * 10 + int(traversal[i])
            i += 1
        node = TreeNode(val)
        while stack and stack[-1][1] >= depth:
            stack.pop()
        if stack:
            parent = stack[-1][0]
            if parent.left is None:
                parent.left = node
            else:
                parent.right = node
        stack.append((node, depth))
    return stack[0][0] if stack else None