转载请注明出处：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;
}
/**************************************************************
Problem: 1350
User: mmc_maodun
Language: C
Result: Accepted
Time:0 ms
Memory:912 kb
****************************************************************/
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/109710.html原文链接：https://javaforall.net
