leetcode 337. 打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

     3
    / 
   2   3
        
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / 
   4   5
  /     
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

解法一

思路：简单 dfs，当前节点如果可以偷，那么当前节点可以选择偷（左右孩子都不可以偷），当前节点选择不偷（左右孩子都可以偷）

main函数的含义是在root 可偷或者不可偷的限制下，以root 为跟的子数最多可以偷多少。

问题：相同的节点会被多次调 rob方法

代码：


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        return main(1, root);
    }
    public int main(int flag, TreeNode root) {
        if (root == null) return 0;
        if (flag == 1) return Math.max(main(1, root.left)+main(1, root.right), main(0, root.left)+main(0, root.right)+root.val);
        else return main(1, root.left)+main(1, root.right);
    }
}

解法二

思路：空间换时间，避免重复计算

代码：类似解法一，在返回结果之前用一个map保存输出和输出

问题：多了一些set的操作和空间的占用

解法三

思路：其实在用解法一解题的时候，应该隐隐约约会感觉到父节点的结果是和子节点相关的，有一个递推关系。如果理解解法一可以很轻易的写出递推公式。

但是大家如果没有经验的话还是很难想到这道题的dp解法，因为普通dp是数组形式，这个是树形式的，数据的dp结束于dp[n]那么树状dp结束于dp[root] ，那么就必须是从叶子节点触发，最终结束于根节点

怎么才能从叶子节点出发，结束于根节点呢？1、二叉树遍历为数组，操作数组（太麻烦了）2、递归

所以这道题就算是dp也是要递归的，如果可以想到这里，那么就很简单了，从第一题的 "父节点告诉子节点自己有没有被`打劫`" 变成 "子节点告诉父节点自己被打劫和不被打劫分别所能返回的最优结果"

问题就迎刃而解了

好处：所有节点都只会处理一遍，没有了map的操作

代码：

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

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

        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = root.val + left[0] + right[0];
        
        return res;
    }
}