转载请注明出处：http://blog.csdn.net/ns_code/article/details/27249675

题目描写叙述：

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

输入：

第一行输入有n，n表示结点数，结点号从1到n。根结点为1。 n <= 10。

接下来有n行，每行有两个个整型a和b，表示第i个节点的左右孩子孩子。a为左孩子，b为右孩子。当a为-1时，没有左孩子。当b为-1时，没有右孩子。

输出：

输出一个整型，表示树的深度。

例子输入：

3

2 3

-1 -1

-1 -1

例子输出：

2

之前在Cracking the Coding interview中有一道依据给定有序数组，创建一个高度最小的二叉树的题目，最后要写个求高度的函数，与这道题一样。这是这次用数组存储二叉树，在九度OJ上AC。

思路非常easy，递归实现，代码例如以下：

#include<stdio.h>

#include<stdlib.h>

typedef struct BTNode

{

	int data;

	int rchild;

	int lchild;

}BTNode;

int max(int a,int b)

{

	return a>b ? a:b;

}

/*

求二叉树的深度

*/

int TreeDepth(BTNode *pTree,int index)

{

	if(pTree == NULL)

		return 0;

	if(index == -1)

		return 0;

	else

		return max(TreeDepth(pTree,pTree[index].lchild),TreeDepth(pTree,pTree[index].rchild)) + 1;

}

int main()

{

	int n;

	while(scanf("%d",&n) != EOF)

	{

		BTNode *pTree = NULL;

		if(n>0)

		{

			pTree = (BTNode *)malloc(n*sizeof(BTNode));

			if(pTree == NULL)

				exit(EXIT_FAILURE);

			int i;

			//输入n个节点的data

			for(i=0;i<n;i++)

			{

				int data1,data2;

				scanf("%d %d",&data1,&data2);

				if(data1 != -1)

					pTree[i].lchild = data1-1;

				else

					pTree[i].lchild = -1;

				if(data2 != -1)

					pTree[i].rchild = data2-1;

				else

					pTree[i].rchild = -1;

			}

		}

		printf("%d",TreeDepth(pTree,0));

	}

	return 0;

}