8000 refactor 337 · sakurazz/Leetcode-1@e565826 · GitHub
[go: up one dir, main page]
Skip to content

Commit e565826

Browse files
fishercoder1534fishercoder1534
committed
refactor 337
1 parent 28c35ff commit e565826

File tree

1 file changed

+41
-36
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+41
-36
lines changed

‎src/main/java/com/fishercoder/solutions/_337.java

Lines changed: 41 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -19,62 +19,67 @@
1919
3
2020
/ \
2121
2 3
22-
\ \
22+
\ \
2323
3 1
2424
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
2525
2626
Example 2:
2727
3
2828
/ \
2929
4 5
30-
/ \ \
30+
/ \ \
3131
1 3 1
3232
Maximum amount of money the thief can rob = 4 + 5 = 9.
3333
*/
3434

3535
public class _337 {
3636

37-
//same idea, but with cacheing via a hashmap: 8 ms
38-
public int rob_dp(TreeNode root) {
39-
Map<TreeNode, Integer> map = new HashMap<>();
40-
return getMaxValue(root, map);
41-
}
42-
43-
private int getMaxValue(TreeNode root, Map<TreeNode, Integer> map) {
44-
if (root == null) {
45-
return 0;
46-
}
47-
if (map.containsKey(root)) {
48-
return map.get(root);
49-
}
37+
public static class Solution1 {
38+
//simple recursion without cacheing: 1189 ms
39+
public int rob(TreeNode root) {
40+
if (root == null) {
41+
return 0;
42+
}
5043

51-
int val = 0;
52-
if (root.left != null) {
53-
val += getMaxValue(root.left.left, map) + getMaxValue(root.left.right, map);
44+
int val = 0;
45+
if (root.left != null) {
46+
val += rob(root.left.left) + rob(root.left.right);
47+
}
48+
if (root.right != null) {
49+
val += rob(root.right.left) + rob(root.right.right);
50+
}
51+
val = Math.max(val + root.val, rob(root.left) + rob(root.right));
52+
return val;
5453
}
55-
if (root.right != null) {
56-
val += getMaxValue(root.right.left, map) + getMaxValue(root.right.right, map);
57-
}
58-
int max = Math.max(root.val + val, getMaxValue(root.left, map) + getMaxValue(root.right, map));
59-
map.put(root, max);
60-
return max;
6154
}
6255

63-
//simple recursion without cacheing: 1189 ms
64-
public int rob(TreeNode root) {
65-
if (root == null) {
66-
return 0;
56+
public static class Solution2 {
57+
//same idea, but with cacheing via a hashmap: 8 ms
58+
public int rob_dp(TreeNode root) {
59+
Map<TreeNode, Integer> map = new HashMap<>();
60+
return getMaxValue(root, map);
6761
}
6862

69-
int val = 0;
70-
if (root.left != null) {
71-
val += rob(root.left.left) + rob(root.left.right);
72-
}
73-
if (root.right != null) {
74-
val += rob(root.right.left) + rob(root.right.right);
63+
private int getMaxValue(TreeNode root, Map<TreeNode, Integer> map) {
64+
if (root == null) {
65+
return 0;
66+
}
67+
if (map.containsKey(root)) {
68+
return map.get(root);
69+
}
70+
71+
int val = 0;
72+
if (root.left != null) {
73+
val += getMaxValue(root.left.left, map) + getMaxValue(root.left.right, map);
74+
}
75+
if (root.right != null) {
76+
val += getMaxValue(root.right.left, map) + getMaxValue(root.right.right, map);
77+
}
78+
int max = Math.max(root.val + val,
79+
getMaxValue(root.left, map) + getMaxValue(root.right, map));
80+
map.put(root, max);
81+
return max;
7582
}
76-
val = Math.max(val + root.val, rob(root.left) + rob(root.right));
77-
return val;
7883
}
7984

8085
}

0 commit comments

Comments
 (0)
0