题目要求比较简单，写一程序求一棵二叉树中相距最远的两个节点之间的距离。
其实第一眼就能相当用递归是最简单也是最直观的：
以当前节点v为根的子树中两节点的最远距离有三种情况：
1、距离最远的两个节点均在v的左子树
2、距离最远的两个节点均在v的右子树
3、距离最远的两个节点一个在左子树一个在右子树（或者v就是其中一个节点）
对于第三种情况，只需要计算左子树的高度和右子树的高度，然后相加即可；
对于第一种和第二种情况，则需要知道左子树的最远距离，以及右子树的最远距离；
因此数据结构如下：
1 struct Node {
2 int value;
3 int left_height;
4 int right_height;
5 Node *left;
6 Node *right;
7 };
其中left_height和right_height记录左右子树的高度；
函数实现如下：
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 }
函数有一个返回值，用于返回以t为根的树的最远距离。
posted on 2012-09-03 17:12
myjfm 阅读(2285)
评论(0) 编辑 收藏 引用 所属分类:
算法基础