题目：

有一颗树，不一定是二叉树，有n个节点，编号为0到n-1。有一个数组A，数组的索引为0到n-1，数组的值A[i]表示节点i的父节点的id，根节点的父节点id为-1。给定数组A，求得树的高度。

分析：

这个题目我们把数组写出来，然后分析，就很明了了。如下例子：

值	3	3	3	-1	2
index	0	1	2	3	4

根据题意：

节点0，1，2的父节点为3

节点3是根节点

节点4的父节点为2

解法：

一个直接的解法是，遍历数组A中的每一个元素，回溯到根节点，得到这个节点的高度。遍历完毕数组之后，取最大的，就是树的高度。上面的例子大概过程如下：

0->3->-1，得到0到根的高度为2，同理1->3->-1，2->3->-1

3->-1，高度就是1

4->2->3->1，得到高度为3

综上，最大的高度为3，则树的高度为3。这个方法的时间复杂度为O(n²)，空间复杂度为O(1)。

 

程序代码：

public static int getTreeHigh()    {        int high = 0;        for(int i=0;i<A.length;i++)        {            int count = 0;            int flag = i;            while(flag!=-1)            {                flag = A[flag];                count++;            }            if(count > high)            {                high = count;            }        }        return high;        }

那么，是否能够继续改进呢？通过上面的计算过程，我们可以发现，在计算4->2->3->-1的时候，显然2->3->-1已经计算过了，不需要再浪费时间重新计算一遍。示例代码如下：

public static int countDepth()    {        int [] high = new int[A.length];        for(int i = 0;i<A.length;i++)            high[i] = -1;        int maxHigh  = -1;        for(int i=0;i<A.length;i++)        {            if(high[i]== -1)            {                if(maxHigh<findHigh(i, high))                {                    maxHigh = findHigh(i, high);                }            }        }        return maxHigh;    }    private static int findHigh(int i,int [] high)    {        if(high[i]!=-1)            return high[i];        if(A[i]==-1)        {            high[i] = 1;        }        else {            high[i] = 1 + findHigh(A[i], high);        }        return high[i];    }

树的高度