首页 / 软件开发 / 数据结构与算法 / 如何求二叉树深度

如何求二叉树深度2015-10-30题目描述：

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

输入：

第一行输入有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。

思路很简单，递归实现，代码如下：

#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;elsereturn 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个节点的datafor（i=0;i<n;i++）{int data1,data2;scanf（"%d %d",&data1,&data2）;if（data1 ！= -1）pTree[i].lchild = data1-1;elsepTree[i].lchild = -1;if（data2 ！= -1）pTree[i].rchild = data2-1;elsepTree[i].rchild = -1;}}printf（"%d",TreeDepth（pTree,0））;}return 0;}