Java DP solution with explanation
/**\n     * Let S(k, r) represent the state of robbed money, where k is current node and r is whether to rob k (=1) or not (=0),\n     * therefore, S(k, r) can 
    /**\n     * Let S(k, r) represent the state of robbed money, where k is current node and r is whether to rob k (=1) or not (=0),\n     * therefore, S(k, r) can be read as "the amount of money can be robbed at node k, either to rob k (r=1) or not to rob k (r=0)"\n     *\n     * Then, the state can be calculated via:\n     *   S(k,0) = max{S(k.left, 0), S(k.left, 1)} + max{S(k.right, 0), S(k.right, 1)}\n     *   S(k,1) = k.val + S(k.left, 0) + S(k.right, 0)\n     * \n     * Finally, the max amount of money can be robbed at root node is max{S(root,0), S(root,1)}\n     */\n    public class Solution {\n    \n        private Map<TreeNode, Integer> rob = new HashMap<>();\n        private Map<TreeNode, Integer> norob = new HashMap<>();\n    \n        public int rob(TreeNode root) {\n            return Math.max(robHelper(root, true), robHelper(root, false));\n        }\n        \n        private int robHelper(TreeNode root, boolean robRoot) {\n            if (root == null) {\n                return 0;\n            }\n            \n            if (robRoot) {\n                if (rob.containsKey(root)) {\n                    // Solved case\n                    return rob.get(root);\n                } else {\n                    int money = root.val + robHelper(root.left, false) + robHelper(root.right, false);\n                    rob.put(root, money);\n                    return money;\n                }\n            } else {\n                if (norob.containsKey(root)) {\n                    // Solved case\n                    return norob.get(root);\n                } else {\n                    int leftMax = Math.max(robHelper(root.left, false), robHelper(root.left, true));\n                    int rightMax = Math.max(robHelper(root.right, false), robHelper(root.right, true));\n                    int money = leftMax + rightMax;\n                    norob.put(root, money);\n                    return money;\n                }\n            }\n        }\n    }
['Dynamic Programming', 'Java']