package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/house-robber-iii/
 */
public class Problem337 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Map<String, Integer> memo = new HashMap<>();
        int a = rob(root, false, memo);
        int b = rob(root, true, memo);
        System.out.println("a: " + a + " vs b: " + b);
        return Math.max(a, b);
    }

    private int rob(TreeNode node, boolean skipped, Map<String, Integer> memo) {
        if (node == null) {
            return 0;
        }
        int max;
        if (skipped) {
            int left1 = rob(node.left, skipped, memo); // continue skipping
            int left2 = rob(node.left, !skipped, memo); // start processing
            int maxLeft = Math.max(left1, left2);

            int right1 = rob(node.right, skipped, memo); // continue skipping
            int right2 = rob(node.right, !skipped, memo); // start processing
            int maxRight = Math.max(right1, right2);

            max = maxLeft + maxRight;
        } else { // not skipped
            int left = rob(node.left, skipped, memo); // start skipping
            int right = rob(node.right, skipped, memo); // start skipping
            max = left + right;
        }
        if (!skipped) {
            max += node.val;
        }
        return max;
    }

    public static void main(String[] args) {
        Problem337 prob = new Problem337();

        TreeNode root = new TreeNode(3);
//        root.left = new TreeNode(2);
//        root.left.right = new TreeNode(3);
//        root.right = new TreeNode(3);
//        root.right.right = new TreeNode(1);
//        System.out.println(prob.rob(root)); // 7
//
//        root = new TreeNode(3);
//        root.left = new TreeNode(4);
//        root.left.left = new TreeNode(1);
//        root.left.right = new TreeNode(3);
//        root.right = new TreeNode(5);
//        root.right.right = new TreeNode(1);
//        System.out.println(prob.rob(root)); // 9
//
//        root = new TreeNode(4);
//        root.left = new TreeNode(1);
//        root.left.left = new TreeNode(2);
//        root.left.left.left = new TreeNode(3);
//        System.out.println(prob.rob(root)); // 7
//
//        root = new TreeNode(3);
//        System.out.println(prob.rob(root)); // 3
//
//        root = new TreeNode(3);
//        root.left = new TreeNode(1);
//        root.right = new TreeNode(3);
//        System.out.println(prob.rob(root)); // 4

        root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(3);
        System.out.println(prob.rob(root)); // 7
    }
}

@@ -298,24 +298,262 @@
 x;%0A        %7D
+%0A%0A        @Override%0A        public String toString() %7B%0A            final StringBuilder sb = new StringBuilder(%22TreeNode%7B%22);%0A            sb.append(%22val=%22).append(val);%0A            sb.append('%7D');%0A            return sb.toString();%0A        %7D
 %0A    %7D%0A%0A    
@@ -768,32 +768,34 @@
 t, true, memo);%0A
+//
         System.o
@@ -829,24 +829,24 @@
  b: %22 + b);%0A
-
         retu
@@ -1551,17 +1551,20 @@
     int 
-l
+maxL
 eft = ro
@@ -1568,32 +1568,33 @@
  rob(node.left, 
+!
 skipped, memo); 
@@ -1623,25 +1623,28 @@
         int 
-r
+maxR
 ight = rob(n
@@ -1646,32 +1646,33 @@
 rob(node.right, 
+!
 skipped, memo); 
@@ -1711,16 +1711,22 @@
 x = 
-l
+maxL
 eft + 
-r
+maxR
 ight
@@ -1950,34 +1950,32 @@
 ew TreeNode(3);%0A
-//
         root.lef
@@ -1987,34 +1987,32 @@
 ew TreeNode(2);%0A
-//
         root.lef
@@ -2030,34 +2030,32 @@
 ew TreeNode(3);%0A
-//
         root.rig
@@ -2068,34 +2068,32 @@
 ew TreeNode(3);%0A
-//
         root.rig
@@ -2112,34 +2112,32 @@
 ew TreeNode(1);%0A
-//
         System.o
@@ -2161,37 +2161,33 @@
 ob(root)); // 7%0A
-//%0A//
+%0A
         root = n
@@ -2194,34 +2194,32 @@
 ew TreeNode(3);%0A
-//
         root.lef
@@ -2231,34 +2231,32 @@
 ew TreeNode(4);%0A
-//
         root.lef
@@ -2273,34 +2273,32 @@
 ew TreeNode(1);%0A
-//
         root.lef
@@ -2316,34 +2316,32 @@
 ew TreeNode(3);%0A
-//
         root.rig
@@ -2362,18 +2362,16 @@
 ode(5);%0A
-//
         
@@ -2398,34 +2398,32 @@
 ew TreeNode(1);%0A
-//
         System.o
@@ -2455,21 +2455,17 @@
 ); // 9%0A
-//%0A//
+%0A
         
@@ -2488,18 +2488,16 @@
 ode(4);%0A
-//
         
@@ -2517,34 +2517,32 @@
 ew TreeNode(1);%0A
-//
         root.lef
@@ -2567,18 +2567,16 @@
 ode(2);%0A
-//
         
@@ -2606,34 +2606,32 @@
 ew TreeNode(3);%0A
-//
         System.o
@@ -2663,21 +2663,17 @@
 ); // 7%0A
-//%0A//
+%0A
         
@@ -2688,34 +2688,32 @@
 ew TreeNode(3);%0A
-//
         System.o
@@ -2749,13 +2749,9 @@
 / 3%0A
-//%0A//
+%0A
     
@@ -2770,34 +2770,32 @@
 ew TreeNode(3);%0A
-//
         root.lef
@@ -2815,18 +2815,16 @@
 ode(1);%0A
-//
         
@@ -2853,18 +2853,16 @@
 ode(3);%0A
-//
         

Update problem 337