首页 > ACM题库 > 九度OJ > 剑指offer(14)-二叉树的深度[数据结构]
2014
02-13

剑指offer(14)-二叉树的深度[数据结构]

题目来自九度剑指offer系列:九度-1350-二叉树的深度

题目描述:
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
输入:
第一行输入有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

 

二叉树的题一般用递归,没什么难度。数据结构的练习题。

#include<stdio.h>

int a[20][2];

int TreeDepth(int i,int n)
{

    if (i==-1)
    {
        return 0;
    }

    int ldep =0;
    if (a[i-1][0]!=-1)
    {
        ldep = TreeDepth(a[i-1][0],n);
    }
    int rdep =0;
    if (a[i-1][1]!=-1)
    {
        rdep =  TreeDepth(a[i-1][1],n);
    }
    return ldep>rdep?ldep+1:rdep+1;
}

int main()
{

    int n;
    while(~scanf("%d",&n))
    {
        int i;
        for (i=0;i<n;i++)
        {
            scanf("%d%d",&a[i][0],&a[i][1]);    
        }
        int depth = TreeDepth(1,n);
        printf("%d\n",depth);
    }
    return 0;
}

/**************************************************************
    Problem: 1350
    User: 从此醉
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1020 kb
****************************************************************/

 


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?