1026. Family Tree Floors
A property portal draws a family tree one generation at a time. You are given root, the oldest ancestor of a tree in which each person may have any number of children, stored in left-to-right order. Produce the rows of the diagram: the first row holds the root, the next row holds all of the root's children, the row after that all grandchildren, and so on. Each row is read from left to right.
Return the rows as a 2D integer array of person values. If root is null, return an empty array. The solution should run in O(n) time and O(w) extra space, where n is the number of people and w the widest generation.
Example 1
- Input:
- root = [1,null,2,3,4,null,5,null,null,6,7]
- Output:
- [[1],[2,3,4],[5,6,7]]
- Explanation:
Generation one is [1], generation two is the children [2, 3, 4], and generation three is the grandchildren [5, 6, 7] read left to right.
Example 2
- Input:
- root = [9,null,8,7,null,null,6]
- Output:
- [[9],[8,7],[6]]
- Explanation:
The root forms the first row, its children 8 and 7 form the second, and the only grandchild 6 forms the third.
Constraints
0 ≤ number of nodes n ≤ 105
-104 ≤ node value ≤ 104
A node may have any number of children; the tree is given as a rooted N-ary tree.
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(w)