继打家劫舍前两题之后的第三题，普通DP->环形DP->树形DP

题目

核心思想

与前两题题意类似，都是不能偷窃相邻的结点，不过在树形结构中，相邻结点变成如下所示

一个结点的相邻结点包括其父节点、子节点，最多有三个，问题看似复杂了，不过核心思路还是一样的。

划分子问题

与前两题思想一致，对于每一个结点，都有偷和不偷两种选择，而当前结点偷了的话，其子节点就不能偷。也就是说，我们只能去考虑其孙子结点偷或者不偷(相当于dp[i + 2])；当前结点不偷的话，直接考虑其子节点偷或者不偷(相当于dp[i + 1])。因此对这两种选择取最大值即可得到状态转移方程。

状态转移方程

/* 偷当前结点root，那么需要考虑他的四个孙子结点 */
int steal = root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right);
/* 不偷当前结点，只需考虑其两个儿子结点 */
int notSteal = rob(root.left) + rob(root.right);
/* 返回两者最大值即可 */
return Math.max(steal, notSteal);

有了状态转移方程，只需要在递归调用之前判断要访问的结点是否为空即可，完整代码如下：

class Solution {
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }

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

优化

提交后可以发现耗时很大，需要思考一下怎么优化。通过上边图可以想到，当前结点需要访问其孙子结点，而当前结点的子节点在更深层的递归中也要访问这几个结点，重复占用了很长的时间。所以一种比较直接的想法就是使用一个字典，用结点作为键，结点能获取的最多的钱数作为值，这样只需要访问开始的四个孙子结点即可，后续的访问递归由于深层次的结点访问过了，值都存在map中，就省去了递归的时间，代码如下：

class Solution {
    private HashMap<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();

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

        return money;
    }
}

提交过后发现虽然优化快了很多，还是只超过50%左右的提交，苦思冥想也没想到更好的优化办法，参考了题解：

class Solution {
    public int rob(TreeNode root) {
        int[] thisMoney = robMoney(root);
        return Math.max(thisMoney[0], thisMoney[1]);
    }

    public int[] robMoney(TreeNode root) {
        int[] thisMoney = new int[2];
        if (root == null) {
            return thisMoney;
        }
        int[] left = robMoney(root.left);
        int[] right = robMoney(root.right);
        thisMoney[0] = Math.max(left[1], left[0]) + Math.max(right[0], right[1]);
        thisMoney[1] = root.val + left[0] + right[0];
        return thisMoney;
    }
}

这种方法真的很巧妙，将返回值设置为一个长度为2的数组，0位存储不偷的最大钱数，1位存储偷的最大钱数，这样就省去了对孙子结点的思考，因为子节点不偷的情况也就包含了孙子结点偷或不偷的最大值，无须重复递归计算。每一层递归只需要返回一个长度为2的数组，省去了对map维护所需要的时间，耗时一下就缩减了很多。不过确实不是很好想到，还是需要慢慢积累啊