Leetcode Problem 1028. Recover a Tree From Preorder Traversal

1028. Recover a Tree From Preorder Traversal

Leetcode Solutions

Iterative Stack Solution

  1. Initialize an empty stack to keep track of nodes.
  2. Initialize variables to keep track of the current index in the string, the current depth, and the current node's value.
  3. Iterate through the traversal string. a. Count the number of dashes to determine the current depth. b. Parse the next number to determine the node's value. c. If the stack size is greater than the current depth, pop from the stack until the sizes match. d. Create a new node with the parsed value. e. If the stack is not empty, add the new node as a left or right child of the node at the top of the stack. f. Push the new node onto the stack.
  4. After the loop, the root of the tree will be at the bottom of the stack. Pop all other nodes and return the root.
UML Thumbnail

Recursive Depth Tracking Solution

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...