Recover a Tree From Preorder Traversal - LeetCode
We run a preorder depth-first search (DFS) on the root of a binary tree. At each node in this traversal, we output D…
We run a preorder depth-first search (DFS) on the
root of a binary tree.
At each node in this traversal, we output
D dashes (where
D is the depth of this node), then we output the value of this node. If the depth of a node is
D, the depth of its immediate child is
D + 1. The depth of the
root node is
If a node has only one child, that child is guaranteed to be the left child.
Given the output
traversal of this traversal, recover the tree and return its
Input: traversal = "1-2--3--4-5--6--7"
Input: traversal = "1-2--3---4-5--6---7"
Input: traversal = "1-401--349---90--88"
- The number of nodes in the original tree is in the range
1 <= Node.val <= 109
- we will see dashes and value, so we verify it’s level and value while scan through the string
- because it’s in-order traversal, if the stack.size bigger than level, will pop out from the stack
- if the stack.peek().left is null, will add it into stack.peek().left; else add it into stack.peek().right
- to return the result, which is the root. We will need to pop all the other TreeNode in stack, until the last one -> the root
- Trick: use three variable in two for loops. Track index, level and value at the same time. Make sure index is not larger than string.length, to avoid overflow.