1022. Family Tree Depth
A genealogy app keeps a family tree in which every person can have any number of children. You are given root, the ancestor at the top of the tree (or null when the tree is empty). Count how many generations the tree spans: the number of people on the longest path that starts at root and walks down through children until it reaches someone with no children.
Return that count as an integer. An empty tree has 0 generations and a tree holding only the root has 1. Aim for O(n) time, where n is the number of people, and avoid deep recursion because a single family line can be very long.
Example 1
- Input:
- root = [1,null,2,3,null,null,4]
- Output:
- 3
- Explanation:
The longest line of descent is 1, 3, 4, which contains three people, so the answer is 3.
Example 2
- Input:
- root = [4,null,9,7,null,2,6,null,null,null,1]
- Output:
- 4
- Explanation:
The deepest chain is 4, 9, 6, 1 with four people; the other branches are shorter.
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)