fd

dingjikerbo · dingjikerbo · commit 30005133c13a · 2018-09-16T07:32:08.000+08:00
diff --git a/leetcode/solution/src/HouseRobberIII.java b/leetcode/solution/src/HouseRobberIII.java
@@ -1,5 +1,8 @@
 public class HouseRobberIII {
 
+    /**
+     * 效率堪忧，耗时1000ms
+     */
     public int rob(TreeNode root) {
         return rob(root, true);
     }
@@ -19,4 +22,25 @@ private int rob(TreeNode root, boolean rob) {
             return rob(root.left, true) + rob(root.right, true);
         }
     }
+
+    /**
+     * 优化写法如下，耗时1ms
+     */
+    public int rob2(TreeNode root) {
+        int[] val = helper(root);
+        return Math.max(val[0], val[1]);
+    }
+
+    private int[] helper(TreeNode node) {
+        if (node == null) {
+            return new int[]{0,0};
+        }
+        int[] left = helper(node.left);
+        int[] right = helper(node.right);
+        int[] value = new int[2];
+        value[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
+        value[1] = node.val + left[0] + right[0];
+        return value;
+    }
+
 }
diff --git a/leetcode/src/Main.java b/leetcode/src/Main.java
@@ -4,21 +4,21 @@
 
 public class Main {
 
-    public int kthSmallest(TreeNode root, int k) {
-        Stack<TreeNode> stack = new Stack<>();
-        while (!stack.isEmpty() || root != null) {
-            if (root != null) {
-                stack.push(root);
-                root = root.left;
-            } else {
-                root = stack.pop();
-                if (--k == 0) {
-                    return root.val;
-                }
-                root = root.right;
-            }
+    public int rob(TreeNode root) {
+        int[] val = helper(root);
+        return Math.max(val[0], val[1]);
+    }
+
+    private int[] helper(TreeNode node) {
+        if (node == null) {
+            return new int[]{0,0};
         }
-        return 0;
+        int[] left = helper(node.left);
+        int[] right = helper(node.right);
+        int[] value = new int[2];
+        value[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
+        value[1] = node.val + left[0] + right[0];
+        return value;
     }
 
     public static void main(String[] args) {
