剑指Offer - 九度1350 - 二叉树的深度

剑指Offer - 九度1350 - 二叉树的深度
2013-11-23 00:54

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

输入：

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

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

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

样例输入：

样例输出：

题意分析：
　　题目要求求出二叉树的深度，也就是根节点到最远叶结点的长度。思路很清楚，DFS。
　　递归关系为：

　　　　max_depth(NULL) = 0;
　　　　max_depth(r) = max(max_depth(r->left), max_depth(r->right)) + 1;

　　实际上由于树的节点个数一开始就指定了，所以直接用数组存数据，用下标当指针就行了，coding更方便。题目中节点数n的数据范围居然只有10，我都怀疑应该是10000或者1000错写成10了。
　　但有一点要注意，根节点如果不指定为1的话，是需要我们自己去判断哪个是根节点的。对于任何树结构，都只有根节点的入度为零，因为没有节点指向根节点。找出根节点才能去递归。
　　每个节点遍历一次，时间复杂度O(n)。节点数据都要存起来，空间复杂度O(n)。

 // 654348    zhuli19901106    1350    Accepted    点击此处查看所有case的执行结果    1020KB    982B    0MS

 //

 #include <cstdio>

 using namespace std;

 int mymax(const int &a, const int &b)

 {

     return a > b ? a : b;

 }

 int max_depth(const int a[][], int r)

 {

     if(a == NULL || r < ){

         return ;

     }

     return mymax(max_depth(a, a[r][]), max_depth(a, a[r][])) + ;

 }

 int main()

 {

     const int MAXN = ;

     int a[MAXN][];

     int in_degree[MAXN];

     int i, n;

     while(scanf("%d", &n) == ){

         if(n < ){

             printf("0\n");

             continue;

         }

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

             in_degree[i] = ;

         }

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

             scanf("%d%d", &a[i][], &a[i][]);

             if(a[i][] >=  && a[i][] <= n){

                 ++in_degree[a[i][]];

             }

             if(a[i][] >=  && a[i][] <= n){

                 ++in_degree[a[i][]];

             }

         }

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

             if(in_degree[i] == ){

                 break;

             }

         }

         printf("%d\n", max_depth(a, i));

     }

     return ;

 }

巴特西

剑指Offer - 九度1350 - 二叉树的深度

最新文章

热门文章