1615. Flatten by Levels
A company chart is stored as a multilevel doubly linked list: every node has next, prev and child pointers, and a child points to the head of another doubly linked list holding that node's direct reports, which can have reports of their own. Write flattenByLevels(head) to turn it into a single-level list in breadth-first order: first all top-level nodes in order, then every node of depth 2 (child lists taken in the order their parents appear), then depth 3, and so on. Set every child to null, repair the prev links and return the head, or null for an empty list. Test inputs write a child list in brackets right 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)