1028. Family Tree Post-Order
An archive app tidies up a family tree from the bottom: a person's record may only be processed after every record in each of their branches has been processed. 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 processing order: the first child's whole branch, then the second child's branch, and so on, and finally the person themselves.
Return an empty array when root is null. Branches can be 100000 people deep, so use an explicit stack rather than recursion. Aim for O(n) time and O(n) space.
Example 1
- Input:
- root = [1,null,2,3,null,null,4,5]
- Output:
- [2,4,5,3,1]
- Explanation:
The branch of 2 is just 2, the branch of 3 gives 4, 5, 3, and the root 1 comes last.
Example 2
- Input:
- root = [6,null,5,3,null,4]
- Output:
- [4,5,3,6]
- Explanation:
The first branch yields 4 then 5, the second yields 3, and the root 6 is processed last.
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)