A family tree is stored as a binary tree: the root is the founder and every person has at most
two children. Generation d is the set of people at depth d (the founder is generation 0).
The elder of generation d is the deepest person who is an ancestor of every member of
that generation, where a person counts as their own ancestor. (If a generation has one member,
that member is its own elder.)
Return a list whose entry d is the value of the elder of generation d, for every generation
from 0 down to the deepest one. Return [] for an empty tree. Values need not be distinct; you
report the value stored in the elder's node.
Examples
1
/ \
2 3
/ \ \
4 5 6
/
7
Input: root = build_tree([1, 2, 3, 4, 5, None, 6, None, None, 7])
Output: [1, 1, 1, 7]
1
/
2
/ \
3 4
\
5
Input: root = build_tree([1, 2, None, 3, 4, None, None, None, 5])
Output: [1, 2, 2, 5]
Constraints
0 <= number of nodes <= 10**5; the depth can be close to the number of nodes.-10**9 <= node.val <= 10**9- Target complexity: O(n).
Goals
- Find, for every depth, the deepest node that is an ancestor of the whole level
- Notice that this node can only move downwards from one level to the next
- Combine a breadth-first pass with a bottom-up pass, both without recursion