题目描述
给出一个二叉排序树的层次遍历，求从它的一个叶子结点到另一个叶子结点的路径，要求路径上经过结点的数值之和最大。二叉树的层次遍历序列从文件expr.in中读取，结点数值大于0，将结果输出到标准输出中。
样例
input:
1
| 25 15 40 5 20 30 50 10 35
|
output:
算法思路
本题对应模板：求树的直径。
树的直径指的是对于树的任意两个叶子节点最远的距离，即可以简化为对于树中的任意一个节点，到达叶子节点的最长路径和次长路径的长度之和。
基于这一点，可以将求树的直径转化为两个过程
对于自下而上的传递过程，基本的方式和求树的高度相同，但是需要记录次高的路径，但是返回最高的路径。
对于自上而下的过程，需要明确对于任意节点，最长路径和次长路径只会来源于parent和两个children，故需要将parent的某一个长边传递给当前正在计算的节点。通常情况下传入parent的最长边，但是当parent的最长边经过当前点的时候则使用parent的次长边更新当前节点的信息。同时易证使用parent的最长边（次长边）和当前节点的两个长边更新得到的长边必然可以得到以该节点为中心得到的直径长度（并非全局直径）。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| #include <iostream>
#include <fstream>
using namespace std;
const int N = 100010;
int tree[N], mx[N], mx2[N], mxr[N], mx2r[N];
int down(int u)
{
if (!tree[u])
return 0;
int llen = down(u << 1);
int rlen = down((u << 1) + 1);
if (llen > rlen)
mxr[u] = u << 1, mx2r[u] = (u << 1) + 1;
else
mxr[u] = (u << 1) + 1, mx2r[u] = u << 1;
mx[u] = max(llen, rlen) + tree[u];
mx2[u] = min(llen, rlen) + tree[u];
return mx[u];
}
void up(int u, int p)
{
if (!tree[u])
return;
if (p != -1)
{
if (mxr[p] != u)
{
if (mx[p] > mx[u])
{
mx2[u] = mx[u];
mx[u] = mx[p];
mx2r[u] = mxr[u];
mxr[u] = p;
}
else if (mx[p] > mx2[u])
{
mx2[u] = mx[p];
mx2r[u] = p;
}
}
else
{
if (mx2[p] > mx[u])
{
mx2[u] = mx[u];
mx[u] = mx2[p];
mx2r[u] = mxr[u];
mxr[u] = p;
}
else if (mx2[p] > mx2[u])
{
mx2[u] = mx2[p];
mx2r[u] = p;
}
}
}
up(u << 1, u);
up((u << 1) + 1, u);
}
int main()
{
ifstream ifs("expr.in");
int i = 1;
for (; ifs >> tree[i]; i++)
;
down(1);
up(1, -1);
int res = 0;
for (int j = 1; j <= i; ++j)
res = max(res, mx[j] + mx2[j] - tree[j]);
cout << res;
}
|