LeetCode337. 打家劫舍III

// 很好的一道题目，既考察递归又考察动归
// 这个版本超时了，原因是暴搜
// 很显然这里使用的是前序，那是不是应该考虑后序？
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }
        if (root.left != null && root.right != null) {
            return Math.max(rob(root.left) + rob(root.right), root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right));
        }
        if (root.left != null) {
            return Math.max(rob(root.left) + rob(root.right), root.val + rob(root.left.left) + rob(root.left.right));
        }
        return Math.max(rob(root.left) + rob(root.right), root.val + rob(root.right.left) + rob(root.right.right));
    }

上面的代码其实非常的丑陋，就算暴搜也不应该这样写，而是这样

public int rob(TreeNode root) {
        if (root == null)
            return 0;
        int money = root.val;
        if (root.left != null) {
            money += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            money += rob(root.right.left) + rob(root.right.right);
        }
        return Math.max(money, rob(root.left) + rob(root.right));
    }

但这题说到底是树形DP题目，最优解法应该是使用DP，如下

    public int rob(TreeNode root) {
       int[] res = robHelper(root);
       return Math.max(res[0], res[1]); 
    }

    private int[] robHelper(TreeNode root) {
        int[] res = new int[2];
        if (root == null) {
            return res;
        }
        int[] left = robHelper(root.left);
        int[] right = robHelper(root.right);

        // 重点：root不偷，下面的结点一定都是偷吗
        // 分为左右结点，像case1:2偷值为2，不偷为3
        // 如果root不偷，下面的左右都偷反而不一定是最大值
        // root不偷，下面的结点有偷与不偷的权利，根据利益最大化选择偷与不偷
        // 但root偷，下面的结点一定不能偷
        // res[0] = left[1] + right[1];
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = root.val + left[0] + right[0];
        return res;
    }