|
2 | 2 |
|
3 | 3 | importcom.fishercoder.common.classes.TreeNode; |
4 | 4 |
|
| 5 | +importjava.util.HashMap; |
| 6 | +importjava.util.Map; |
| 7 | + |
5 | 8 | /** |
| 9 | + * 124. Binary Tree Maximum Path Sum |
6 | 10 | * Given a binary tree, find the maximum path sum. |
7 | | -
|
8 | | - For this problem, a path is defined as any sequence of nodes from some starting node to any node |
9 | | - in the tree along the parent-child connections. |
| 11 | + * For this problem, a path is defined as any sequence of nodes from some starting node to any node |
| 12 | + * in the tree along the parent-child connections. |
10 | 13 |
|
11 | 14 | The path must contain at least one node and does not need to go through the root. |
12 | 15 |
|
|
21 | 24 | */ |
22 | 25 | publicclass_124 { |
23 | 26 |
|
24 | | -intmax =Integer.MIN_VALUE; |
25 | | - |
26 | | -publicintmaxPathSum(TreeNoderoot) { |
27 | | -dfs(root); |
28 | | -returnmax; |
29 | | - } |
| 27 | +publicstaticclassSolution1 { |
| 28 | +intmax =Integer.MIN_VALUE; |
30 | 29 |
|
31 | | -privateintdfs(TreeNoderoot) { |
32 | | -if (root ==null) { |
33 | | -return0; |
| 30 | +publicintmaxPathSum(TreeNoderoot) { |
| 31 | +dfs(root); |
| 32 | +returnmax; |
34 | 33 | } |
35 | 34 |
|
36 | | -intleft =Math.max(dfs(root.left),0); |
37 | | -intright =Math.max(dfs(root.right),0); |
| 35 | +privateintdfs(TreeNoderoot) { |
| 36 | +if (root ==null) { |
| 37 | +return0; |
| 38 | + } |
| 39 | + |
| 40 | +intleft =Math.max(dfs(root.left),0); |
| 41 | +intright =Math.max(dfs(root.right),0); |
38 | 42 |
|
39 | | -max =Math.max(max,root.val +left +right); |
| 43 | +max =Math.max(max,root.val +left +right); |
40 | 44 |
|
41 | | -returnroot.val +Math.max(left,right); |
| 45 | +returnroot.val +Math.max(left,right); |
| 46 | + } |
42 | 47 | } |
43 | 48 |
|
| 49 | +publicstaticclassSolution2 { |
| 50 | +/**This one uses a map to cache, but surprisingly, it's 10% slower than all submissions compared with solution1*/ |
| 51 | +intmax =Integer.MIN_VALUE; |
| 52 | + |
| 53 | +publicintmaxPathSum(TreeNoderoot) { |
| 54 | +Map<TreeNode,Integer>map =newHashMap<>(); |
| 55 | +dfs(root,map); |
| 56 | +returnmax; |
| 57 | + } |
| 58 | + |
| 59 | +privateintdfs(TreeNoderoot,Map<TreeNode,Integer>map) { |
| 60 | +if (root ==null) { |
| 61 | +return0; |
| 62 | + } |
| 63 | +if (map.containsKey(root)) { |
| 64 | +returnmap.get(root); |
| 65 | + } |
| 66 | +intleft =Math.max(0,dfs(root.left,map)); |
| 67 | +intright =Math.max(0,dfs(root.right,map)); |
| 68 | +max =Math.max(max,root.val +left +right); |
| 69 | +intpathSum =root.val +Math.max(left,right); |
| 70 | +map.put(root,pathSum); |
| 71 | +returnpathSum; |
| 72 | + } |
| 73 | + } |
44 | 74 | } |