house robber III

fishercoder1534 · fishercoder1534 · commit 50f293d4f816 · 2016-08-01T22:12:01.000-07:00
diff --git a/Common/src/classes/TreeNode.java b/Common/src/classes/TreeNode.java
@@ -0,0 +1,8 @@
+package classes;
+
+public class TreeNode {
+    public int val;
+    public TreeNode left;
+    public TreeNode right;
+    public TreeNode(int x){this.val = x;}
+}
diff --git a/MEDIUM/src/medium/HouseRobberIII.java b/MEDIUM/src/medium/HouseRobberIII.java
@@ -0,0 +1,44 @@
+package medium;
+
+import java.util.HashMap;
+import java.util.Map;
+
+import classes.TreeNode;
+
+public class HouseRobberIII {
+
+    //simple recursion without cacheing: 1189 ms
+    public int rob(TreeNode root) {
+        if(root == null) return 0;
+        
+        int val = 0;
+        if(root.left != null){
+            val += rob(root.left.left) + rob(root.left.right);
+        }
+        if(root.right != null){
+            val += rob(root.right.left) + rob(root.right.right);
+        }
+        val = Math.max(val + root.val, rob(root.left) + rob(root.right));
+        return val;
+    }
+    
+    //same idea, but with cacheing via a hashmap: 8 ms
+    public int rob_dp(TreeNode root) {
+        Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
+        return get(root, map);
+    }
+    
+    private int get(TreeNode root, Map<TreeNode, Integer> map){
+        if(root == null) return 0;
+        if(map.containsKey(root)) return map.get(root);
+        
+        int val = 0;
+        if(root.left != null) val += get(root.left.left, map) + get(root.left.right, map);
+        if(root.right != null) val += get(root.right.left, map) + get(root.right.right, map);
+        int max = Math.max(root.val + val, get(root.left, map) + get(root.right, map));
+        map.put(root, max);
+        return max;
+    }
+
+
+}
