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