Maximum Depth of a Rooted Tree
Problem statement
Return the maximum number of nodes on a root-to-leaf path in the tree described by parents.
Nodes are numbered from 0 to parents.length - 1. The root is node 0, with parent -1. For every other node i, parents[i] identifies its parent. Each node may have any number of children, and a parent index may be larger than a child index.
Count nodes, including the root and leaf. A single-node tree has depth 1; an empty tree has depth 0.
Function
maxTreeDepth(parents: int[]) → intExamples
Example 1
parents = [-1,0,0,1,1]return = 3The path 0 → 1 → 3 contains three nodes. No root-to-leaf path contains more, so the maximum depth is 3.
Example 2
parents = [-1]return = 1The root is also a leaf. Its path contains one node, so the depth is 1.
Example 3
parents = []return = 0An empty tree has depth 0.
Constraints
0 <= parents.length <= 5000-1 <= parents[i] <= 4999- For nonempty input,
parents[0] == -1; every other parent is a valid node index. The parent links form one tree rooted at node0, with no cycle.