-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinaryTreeMaximumPathSum.java
More file actions
68 lines (51 loc) · 1.41 KB
/
Copy pathBinaryTreeMaximumPathSum.java
File metadata and controls
68 lines (51 loc) · 1.41 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
// NOT SOLVED!! Small case accepted, but big case failed (runtime error).
/*
* 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
Return 6.
*/
public class BinaryTreeMaximumPathSum {
public static void main(String[] args){
TreeNode n1 = new TreeNode(2);
TreeNode n2 = new TreeNode(1);
n1.left = n2;
System.out.println(maxPathSum(n1));
}
private static class Pair{
Integer v1;
Integer v2;
public Pair(Integer v1, Integer v2){
this.v1 = v1;
this.v2 = v2;
}
}
public static int maxPathSum(TreeNode root) {
Pair p = maxPathSumHelper(root);
return p.v2;
}
public static Pair maxPathSumHelper(TreeNode root){
if(root == null) return new Pair(0,0);
Pair left = maxPathSumHelper(root.left);
Pair right = maxPathSumHelper(root.right);
int v1 = 0;
if(left.v1 <= 0 && right.v1 <= 0 ){
v1 = root.val;
}
else{
v1 = left.v1 > right.v1 ? left.v1 + root.val : right.v1 + root.val;
}
int v2 = ((left.v1 > 0) ? left.v1 : 0 ) + ( (right.v1 > 0) ? right.v1 : 0 ) + root.val;
if (root.right != null){
v2 = ( v2 > right.v2 ) ? v2 : right.v2;
}
if (root.left != null){
v2 = ( v2 > left.v2 ) ? v2 : left.v2;
}
return new Pair(v1,v2);
}
}