1617. Siblings Before Children
A menu system stores its entries in a multilevel doubly linked list: each node has next, prev and child, and a child points to the head of a sub-menu list. Write siblingsFirst(head) to flatten it so that each list appears whole before any of its descendants. Define output(list) as the nodes of that list in order, followed by output(child list of the 1st node), then output(child list of the 2nd node), and so on for every node that has a child. Set every child to null, fix the prev links and return the head (null if empty). Test inputs put a child list in brackets after its parent, like [1,2,[3,[7,8]],4]. There are 0 to 1000 nodes and depth at most 50. Aim for O(n) time.
Example 1
- Input:
- head = [[1,[2,3]],4]
- Output:
- [1,4,2,3]
- Explanation:
Top level is 1 and 4; the child list 2, 3 of node 1 follows.
Example 2
- Input:
- head = [10,[20,[[30,[50,60]],40]],70]
- Output:
- [10,20,70,30,40,50,60]
- Explanation:
Three levels deep, with a child list hanging from a child node.
Example 3
- Input:
- head = [5,6,7]
- Output:
- [5,6,7]
- Explanation:
No node has a child, so the list is already flat.
Constraints
0 ≤ total nodes ≤ 1000
depth ≤ 50
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(n)