_1028. Recover a Tree From Preorder Traversal.md

1028. Recover a Tree From Preorder Traversal

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 01, 2024

Last updated : July 01, 2024

---

Related Topics : String, Tree, Depth-First Search, Binary Tree

Acceptance Rate : 75.2 %

---

Solutions

• h1028.py

Python

h1028.py

# 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
class Solution:
    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
        depths = list(reversed([len(x) for x in re.findall('-{1,9999}', traversal)]))
        nodeVals = list(reversed([int(x) for x in re.findall('[0-9]{1,9999}', traversal)]))
        root = TreeNode(val=nodeVals.pop())

        stk = [(0, root)]
        while depths :
            depth = depths[-1]
            val = nodeVals[-1]
            peekDepth, peekNode = stk[-1]

            if depth <= peekDepth :
                stk.pop()
                continue
            
            if peekNode.left :
                peekNode.right = TreeNode(val=val)
                stk.append((depth, peekNode.right))
            else :
                peekNode.left = TreeNode(val=val)
                stk.append((depth, peekNode.left))
            depths.pop()
            nodeVals.pop()

        return root