1028. Recover a Tree From Preorder Traversal
https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
DFS - Recursion
---
BFS
We do not need to traverse the string twice - we can process nodes as we discover them.
As we discover a new node, we need to know whether this is left or right child of some parent - current level - 1
We need a data structure to lookup parent in constant time - HashMap seems appropriate
As soon as we discover a node - put it on the map - with level as key, node as value
If parent node (current level - 1) exists
If parent left child is not set
current node is left child
else
current node is right child
In the future if we get another node at same level as parent, thats the parents right sibling, so that will override / replace the left parent, and we do not need to worry about mixing up multiple parents at same level
Pre Order - Left child, Right child protects us from that
We run a preorder depth first search 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 0.)
If a node has only one child, that child is guaranteed to be the left child.
Given the output
S of this traversal, recover the tree and return its root.
Example 1:
Input: "1-2--3--4-5--6--7" Output: [1,2,5,3,4,6,7]
Example 2:
Input: "1-2--3---4-5--6---7" Output: [1,2,5,3,null,6,null,4,null,7]
Example 3:
Input: "1-401--349---90--88" Output: [1,401,null,349,88,90]
Note:
- The number of nodes in the original tree is between
1and1000. - Each node will have a value between
1and10^9
--
Intuition
DFS - Recursion
Pre Order => Parent, Left Child, Right Child
Preserving this order is important once we parse the string
Elements should be pulled out from the data structure in same order we put them
FIFO => Queue seems appropriate (*)
* Note optimization later
We can parse the string, and capture node val, level it belongs to
Put them in Queue to preserve this order of find
Then we parse this Queue
Remember Pre Order => Node, Left Child, Right Child
As soon as we get a value from Q - thats parent node
If (Q still has elements, and next element level = current (parent) level + 1)
Thats left child - pop it out, and set it to left of current (parent)
Q has reduced now - since left child is out
If (Q still has elements, and next element level = current (parent) level + 1)
Thats right child - pop it out, and set it to left of current (parent)
If next element level < current (parent) level
next element is child of some earlier parent - do nothing here - return current node
if next element level == current level
next element is sibling => child of current nodes parent - do nothing here - return current node
---
BFS
We do not need to traverse the string twice - we can process nodes as we discover them.
As we discover a new node, we need to know whether this is left or right child of some parent - current level - 1
We need a data structure to lookup parent in constant time - HashMap seems appropriate
As soon as we discover a node - put it on the map - with level as key, node as value
If parent node (current level - 1) exists
If parent left child is not set
current node is left child
else
current node is right child
In the future if we get another node at same level as parent, thats the parents right sibling, so that will override / replace the left parent, and we do not need to worry about mixing up multiple parents at same level
Pre Order - Left child, Right child protects us from that
