256
劍指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：二叉樹的深度
* 來源：https://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;
}
最後更新：2017-04-03 12:53:36