題目要求比較簡(jiǎn)單，寫一程序求一棵二叉樹中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。
其實(shí)第一眼就能相當(dāng)用遞歸是最簡(jiǎn)單也是最直觀的：
以當(dāng)前節(jié)點(diǎn)v為根的子樹中兩節(jié)點(diǎn)的最遠(yuǎn)距離有三種情況：
1、距離最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)均在v的左子樹
2、距離最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)均在v的右子樹
3、距離最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)一個(gè)在左子樹一個(gè)在右子樹（或者v就是其中一個(gè)節(jié)點(diǎn)）
對(duì)于第三種情況，只需要計(jì)算左子樹的高度和右子樹的高度，然后相加即可；
對(duì)于第一種和第二種情況，則需要知道左子樹的最遠(yuǎn)距離，以及右子樹的最遠(yuǎn)距離；
因此數(shù)據(jù)結(jié)構(gòu)如下：
1 struct Node {
2 int value;
3 int left_height;
4 int right_height;
5 Node *left;
6 Node *right;
7 };
其中l(wèi)eft_height和right_height記錄左右子樹的高度；
函數(shù)實(shí)現(xiàn)如下：
1 #define max(a, b) ((a) > (b) ? (a) : (b))
2
3 int find_max_len(Node *t) {
4 if (t == NULL) {
5 return 0;
6 }
7
8 int left_max_len = find_max_len(t->left);
9 int right_max_len = find_max_len(t->right);
10
11 if (t->left) {
12 t->left_height = 1 + max(t->left->left_height, t->left->right_height);
13 }
14 if (t->right) {
15 t->right_height = 1 + max(t->right->left_height, t->right->right_height);
16 }
17
18 int max_len = max(left_max_len, right_max_len);
19 max_len = max(max_len, t->left_height + t->right_height);
20
21 return max_len;
22 }
函數(shù)有一個(gè)返回值，用于返回以t為根的樹的最遠(yuǎn)距離。
posted on 2012-09-03 17:12
myjfm 閱讀(2301)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)