求二叉树中距离最远的2个节点的距离
本文中二叉树结构定义为：
|
1
2
3
4
5
6
|
本文中二叉树结构定义为：
struct
Node {
Node* left;
Node* right;
int
data;
};
|
定义：空二叉树的高度为-1，只有根节点的二叉树高度为0，根节点在0层，深度为0。
两个节点的距离为两个节点间最短路径的长度。
求两节点的最远距离，实际就是求二叉树的直径。假设相距最远的两个节点分别为A、B，它们的最近共同父节点（允许一个节点是其自身的父节点）为C，则A到B的距离 = A到C的距离 + B到C的距离。
节点A、B分别在C的左右子树下（假设节点C的左右两子树均包括节点C），不妨假设A在C的左子树上，由假设“A到B的距离最大”，先固定B点不动（即B到C的距离不变），根据上面的公式，可得A到C的距离最大，即点A是C左子树下距离C最远的点，即：
A到C的距离 = C的左子树的高度。
同理， B到C的距离 = C的右子树的高度。
因此，本问题可以转化为：“二叉树每个节点的左右子树高度和的最大值”。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
static
int
tree_height(
const
Node* root,
int
& max_distance)
{
const
int
left_height = root->left ? tree_height(root->left, max_distance) + 1 : 0;
const
int
right_height = root->right ? tree_height(root->right, max_distance) + 1 : 0;
const
int
distance = left_height + right_height;
if
(max_distance < distance) max_distance = distance;
return
(left_height > right_height ? left_height : right_height);
}
int
tree_diameter(
const
Node* root)
{
int
max_distance = 0;
if
(root) tree_height(root, max_distance);
return
max_distance;
}
|
判断二叉树是否平衡二叉树
根据平衡二叉树的定义：每个结点的左右子树的高度差小等于1，只须在计算二叉树高度时，同时判断左右子树的高度差即可。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
static
int
tree_height(
const
Node* root,
bool
& balanced)
{
const
int
left_height = root->left ? tree_height(root->left, balanced) + 1 : 0;
if
(!balanced)
return
0;
const
int
right_height = root->right ? tree_height(root->right, balanced) + 1 : 0;
if
(!balanced)
return
0;
const
int
diff = left_height - right_height;
if
(diff < -1 || diff > 1) balanced =
false
;
return
(left_height > right_height ? left_height : right_height);
}
bool
is_balanced_tree(
const
Node* root)
{
bool
balanced =
true
;
if
(root) tree_height(root, balanced);
return
balanced;
}
|
