arrays - 在给定父数组的情况下查找树的深度

Question

给出父数组 P，其中 P[i] 表示树中第 i 个节点的父节点(树是通用的)。 root 的父级用 -1 表示。我需要找到树的高度/深度。

示例:P = {-1,0,1,6,6,0,0,2,7}。所以 P[1] = 0 表示节点 1 的父节点为 0 等等。

我的方法:

1. Sort P in O(nlogn). This gives P = {-1,0,0,0,1,2,6,6,7}
2. Scan through the array. 
   If a change is observed on going from index i to i+1 then increment depth (depth++).
   eg When going from index 3 to index 4 of sorted P, there is a change from 0 to 1. So increment depth.
   This scanning takes O(n) time
3. depth - 1 is the depth of the tree.

这种方法似乎适用于我尝试过的示例，但我不确定我是否遗漏了它可能会失败的情况。有人可以提供一个反例吗？谢谢

Answer 1

这是不正确的。考虑两个数组:{-1, 0, 0, 1, 1} 和 {-1, 0, 0, 1, 2}。它们变化的次数不同，但这两棵树的高度相同。