Grokking #219 - 2

    Map<TreeNode, Integer> dp = new HashMap<>();

    int traverse(TreeNode root) {
        int val = 0;

        if (root == null)
            return 0;

        if (dp.containsKey(root)) {
            return dp.get(root);
        }

        if (root.left != null) {
            val += traverse(root.left.left) + traverse(root.left.right);
        }
        if (root.right != null) {
            val += traverse(root.right.left) + traverse(root.right.right);
        }

        int cur = Math.max(val + root.val, traverse(root.left) + traverse(root.right));
        dp.put(root, cur);

        return cur;
    }

    public int rob(TreeNode root) {
        return traverse(root);
    }