要注意，一是空路径也可以，所以最小是0。然后要时刻注意路径顶多有两条子路径+根节点组成，所以更新全局最值时和返回上一级的值要注意分清。
|
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
|
#include <climits>using
namespace
std;
int
maxPathHelper(TreeNode *root, int
&max) {
if
(root == NULL) {
return
0;
}
int
root_val = root->val; // root it self
int
max1 = 0;
int
max2 = 0;
for
(int
i = 0; i < root->children.size(); i++) {
int
max_sub = maxPathHelper(root->children[i], max);
if
(max_sub > max1) {
max2 = max1;
max1 = max_sub;
} else
if
(max_sub > max2) {
max2 = max_sub;
}
}
int
local_max = root_val;
int
tmp = root_val + max1;
if
(tmp > local_max) local_max = tmp;
if
(local_max > max) max = local_max;
tmp = root_val + max1 + max2;
if
(tmp > max) max = tmp;
return
local_max;
}/*树结点的定义(请不要在代码中定义该类型)struct TreeNode { int val;
vector<TreeNode*> children; //该结点的儿子结点
};
*/int
maxTreePathSum(TreeNode *root) {
int
max = 0;
maxPathHelper(root, max);
return
max;
} |