forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinary Tree Maximum Path Sum.java
More file actions
executable file
·177 lines (144 loc) · 5.63 KB
/
Copy pathBinary Tree Maximum Path Sum.java
File metadata and controls
executable file
·177 lines (144 loc) · 5.63 KB
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
R
1519634117
tags: Tree, DFS
LeetCode: H
用 PathSumType 比较特别. 没有 data structure的时候, 写起来比较繁琐.
第一次做有点难理解，复杂原因是：因为可能有负值啊。不能乱assume正数。
single path max 的计算是为了给后面的comboMax用的。
如果single path max小于0，那没有什么加到parent上面的意义，所以就被再次刷为0.
combo的三种情况：(root可能小于0)
1. 只有left
2。 只有右边
3. root大于0，那么就left,right,curr全部加起来。
情况1和情况2取一个最大值，然后和情况三比较。做了两个Math.max(). 然后就有了这一层的comboMax
12.11.2015 recap:
So totally, 5 conditions:
(save in single)
left + curr.val OR right + curr.val
(save in combo:)
left, right, OR left + curr.val + right
```
/*
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
Example
Given the below binary tree:
1
/ \
2 3
return 6.
Tags Expand
Divide and Conquer Dynamic Programming Recursion
*/
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
/*
Thoughts:
Don't assume positive integers .
Two ways of picking nodes: 1. Single Path (left or right)has a maximum. 2. Combine them into a final result: combinedPathMax
1. singlePathMax, two results: either pick left+root or right+root.
2. combinedPathMax: take left-max as a whole, take right-max as a whole.
3 possible results: left-max without parent(like...when parent<0), right-max without parent(like...when parent<0), left-max + right-max + parent.
3. Use a special container to store current node's singlePathMax and combinedPathMax.
Note:12.03.2015
It's complex, because we could have nagative number.
Combo is compared through: just left, just right, or combo of all.
*/
public class Solution {
private class PathSumType {
int singlePathMax;
int combinedPathMax;
PathSumType(int singlePathMax, int combinedPathMax) {
this.singlePathMax = singlePathMax;
this.combinedPathMax = combinedPathMax;
}
}
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
public int maxPathSum(TreeNode root) {
PathSumType result = helper(root);
return result.combinedPathMax;
}
public PathSumType helper(TreeNode root) {
if (root == null) {
return new PathSumType(0, Integer.MIN_VALUE);
}
//Divide
PathSumType left = helper(root.left);
PathSumType right = helper(root.right);
//Conquer
//Step 1: prepare single path max for parent-level comparison.
int singlePathMax = Math.max(left.singlePathMax, right.singlePathMax) + root.val;
singlePathMax = Math.max(singlePathMax, 0);//If less than 0, no need to keep, because it only decrease parent-level max.
//first comparison: does not include root node at all(this would be applicable when curr.val < 0, so we take this condition into account)
int combinedPathMax = Math.max(left.combinedPathMax, right.combinedPathMax);
//second comparison:
combinedPathMax = Math.max(combinedPathMax, left.singlePathMax + right.singlePathMax + root.val);
return new PathSumType(singlePathMax, combinedPathMax);
}
}
// Incorrect:
/*
[9,6,-3,null,null,-6,2,null,null,2,null,-6,-6,-6]
Output:
15
Expected:
16
*/
class Solution {
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
int result = 0;
int leftMaxDirectPathSum = Integer.MIN_VALUE;
int rightMaxDirectPathSum = Integer.MIN_VALUE;
int leftMaxComboPathSum = Integer.MIN_VALUE;
int rightMaxComboPathSum = Integer.MIN_VALUE;
if (root.left != null) {
leftMaxDirectPathSum = maxDirectPathSum(root.left);
leftMaxComboPathSum = maxPathSum(root.left);
}
if (root.right != null) {
rightMaxDirectPathSum = maxDirectPathSum(root.right);
rightMaxComboPathSum = maxPathSum(root.right);
}
int maxComboPathSum = root.val;
if (root.left != null) {
maxComboPathSum += leftMaxDirectPathSum;
}
if (root.right != null) {
maxComboPathSum += rightMaxDirectPathSum;
}
int partResultA = Math.max(root.val, Math.max(leftMaxDirectPathSum, rightMaxDirectPathSum));
int partResultB = maxComboPathSum;
if (root.left == null || root.right == null) {
leftMaxDirectPathSum = leftMaxDirectPathSum == Integer.MIN_VALUE ? 0 : leftMaxDirectPathSum;
rightMaxDirectPathSum = rightMaxDirectPathSum == Integer.MIN_VALUE ? 0 : rightMaxDirectPathSum;
}
partResultB = Math.max(partResultB, Math.max(leftMaxDirectPathSum, rightMaxDirectPathSum) + root.val);
result = Math.max(partResultA, partResultB);
return Math.max(Math.max(leftMaxComboPathSum, rightMaxComboPathSum), result);
}
/*
Path that start with root and end with a leaf
*/
public int maxDirectPathSum(TreeNode root) {
if (root == null) {
return 0;
}
return root.val + Math.max(maxDirectPathSum(root.left), maxDirectPathSum(root.right));
}
}
```