Recover a Tree From Preorder Traversal

lcpy gen -n 1028   # by problem number
lcpy gen -s recover_a_tree_from_preorder_traversal   # by problem name

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

Input: traversal = "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]

Input: traversal = "1-401--349---90--88"
Output: [1,401,null,349,88,90]

from leetcode_py import TreeNode


class Solution:
    # Time: O(n) over the traversal length
    # Space: O(depth) for the node stack
    def recover_from_preorder(self, traversal: str) -> TreeNode[int] | None:
        i = 0
        n = len(traversal)
        stack: list[TreeNode[int]] = []
        while i < n:
            depth = 0
            while i < n and traversal[i] == "-":
                depth += 1
                i += 1
            value = 0
            while i < n and traversal[i].isdigit():
                value = value * 10 + int(traversal[i])
                i += 1
            node: TreeNode[int] = TreeNode(value)
            while len(stack) > depth:
                stack.pop()
            if stack:
                if stack[-1].left is None:
                    stack[-1].left = node
                else:
                    stack[-1].right = node
            stack.append(node)
        return stack[0]