10410

Tree Reconstruction
Type:
Tree
Diff: 7.0

Tricks


To solve this problem, first you need to label the entire node with their level in the tree. We can do it by labeling the node 1 as level 1 and then search node i of bfs in dfs ( suppose the position is k) then search node i+1 of bfs in dfs (from k+1 position of the list) list and continue it until you cannot be able to found the (i+1)th   in the dfs list. And make all the node as level L, then repeat the whole process with level L+1, then L+2, then L+3 and so on.

Then the adjacency elements of a node can be found in the dfs. First find two node (a & b) with same level i and there must not have any node with that level between them. Then all the nodes between a & b of level (i+1) is the adjacency of node a.

Related Problems & Topics

536 Tree Recovery   

If you have any advice, complements 

or proposal, please  Send mail to Author

Submit

 

1