剑指Offer之二叉树的深度

【题目】

题目描述：

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

输入：

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

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

输出：

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

样例输入：

32 3-1 -1-1 -1

样例输出：

2

【解析】

通过递归，迭代计算左右子树的深度，+1.

有一个利好的消息是第n个节点数值为n，这样我们就可以利用二维数组来表示树结构。
在程序中利用二维数组来表示树结构，[i][0]为第i个节点的左节点，[i][1]为第i个节点的右节点

【代码】

/*********************************
*   日期：2013-12-06
*   作者：SJF0115
*   题号: 题目1350：二叉树的深度
*   来源：http://ac.jobdu.com/problem.php?pid=1350
*   结果：AC
*   来源：剑指Offer
*   总结：
**********************************/
#include <iostream>
#include <malloc.h>
#include <stdio.h>
using namespace std;
/*
通过递归，迭代计算左右子树的深度，+1.
在程序中利用二维数组来表示树结构，[i][0]为第i个节点的左节点，[i][1]为第i个节点的右节点
*/
int tree[11][2];

int TreeDepth(int n){
    //第n个节点为叶子节点
    if(tree[n][0] == -1 && tree[n][1] == -1){
        return 1;
    }
    int left = 0,right = 0;
    //迭代计算左右子树的深度
    //左子树
    if(tree[n][0]!= -1)
    {
        left = TreeDepth(tree[n][0]);
    }
    //右子树
    if(tree[n][1]!= -1)
    {
        right = TreeDepth(tree[n][1]);
    }
    return 1 + max(left,right);
}

int main() {
    int i,n,height;
    while(scanf("%d",&n) != EOF){
        //用二维数组表示二叉树
        for(i = 1;i <= n;i++){
            scanf("%d %d",&tree[i][0],&tree[i][1]);
        }
        height = TreeDepth(1);
        printf("%d\n",height);
    }//while
    return 0;
}