Leetcode-binary-tree-maximum-path-sum

题目描述

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

1
2
3
  1
/ \
2 3

Return6.


因为我们是无法从孩子结点找到父结点的,所以在考虑这一题的路径时,可以转变成从某一个父结点为原点,加上左孩子为起点的路径和右孩子为起点的路径。然后计算以这个父结点为原点的最大值,和已知的最大值的比较,并从左右孩子中挑一个值较大且大于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
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
83
84
85
86
87
88
89
90
91
/**

\* Definition for binary tree

\* public class TreeNode {

\* int val;

\* TreeNode left;

\* TreeNode right;

\* TreeNode(int x) { val = x; }

\* }

*/

import java.util.*;

public class Solution {

private int maxSum;

public int maxPathSum(TreeNode root) {

​ maxSum = root.val;

​ maxPathSumHelper(root);

return maxSum;

​ }

private int maxPathSumHelper(TreeNode root){

int sum = root.val;

if (root.left == null && root.right == null){

​ updateMaxSum(sum);

return sum;

​ }

int l = 0;

int r = 0;

if (root.left != null){

​ l = maxPathSumHelper(root.left);

​ }

if (root.right != null){

​ r = maxPathSumHelper(root.right);

​ }

int max = Math.max(l, r);

​ updateMaxSum(sum+l+r);

if (max > 0){

​ sum += max;

​ }

​ updateMaxSum(sum);

return sum;

​ }

private int updateMaxSum(int sum){

if (maxSum < sum){

​ maxSum = sum;

​ }

return maxSum;

​ }

}