DepthOfTree.cpp

//原题
//有一个棵树，不一定是二叉树，有n个节点，编号为0到n-1。有一个数组A，数组的索引为0到n-1，数组的值A[i]表示节点i的父节点的id，根节点的父节点id为-1。给定数组A，求得树的高度。
//分析
//这个题目我们首先把数组写出来，然后进一步分析，就很明了了，如下例子：
//
//3	3	3	-1	2
//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^2)，空间复杂度为O(1)。
//
//那么是否能够继续改进呢？通过上面的计算过程，我们可以发现，在计算4->2->3->-1的时候，显然2->3->-1已经计算过了，不需要再浪费时间重新计算一遍。示例代码如下：

class Tree
{
public:
    void Tree(int len);
	int GetLength();
	int CountDepth();
	~Tree();

private:
    int* root;
	int length;
	int FindWeight();
}

Tree::Tree(int len)
{
    length = len;
	root = new int[len];
}

Tree::~Tree()
{
    length = 0;
	delete(root);
	root = NULL;
}

Tree::GetLength()
{
    return length;
}