1027. Family Tree Pre-Order
A museum guide app reads out a family tree by always announcing a person first, then walking through each of their branches in order. You are given root, the top ancestor of a tree where each person may have any number of children listed left to right. Return the values in the order they would be announced: the person, then everything in the first child's branch, then everything in the second child's branch, and so on.
Return an empty array when root is null. A single family line may contain 100000 people, so do not rely on recursion; use an explicit stack. Aim for O(n) time and O(n) space.
Example 1
- Input:
- root = [1,null,2,3,null,null,4,5]
- Output:
- [1,2,3,4,5]
- Explanation:
Announce 1, then the whole branch of 2, then the branch of 3 which announces 3, 4 and 5.
Example 2
- Input:
- root = [6,null,5,3,null,4]
- Output:
- [6,5,4,3]
- Explanation:
Announce 6, then the first branch (5 and its child 4), then the second branch containing only 3.
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(n)