要注意，一是空路径也可以，所以最小是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;} |
原文：http://www.cnblogs.com/lautsie/p/3526041.html