337. 打家劫舍 III

一 题目：

二 思路：

动态规划
这道题目和之前的打家劫舍1特别像，就是之前是一条链表街打劫，现在是一个二叉树打劫，都是一个相邻结点被触发的报警问题。

这题我们先分析一下，相邻结点不能被同时触发，也就是说父子结点不能被同时被偷
那么我们可以转换思路划分子问题为：

• 当前结点被不被打劫
• 当前结点被打劫

如果当前结点被打劫了，那么其孩子结点就不能有被打劫的，如果当前结点没被打劫，那么孩子结点就无所谓了。

这道题目的话我们就可以通过后续遍历的方法把所有可能情况进行向上的汇总，用下层多路的可能性去判断上层的可能收益问题；

三 代码：

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


    /**
     * int[] 存储当前结点偷不偷的获益情况
     * 0代表不偷，1代表偷
     *
     */
    private int[] dfs(TreeNode root) {
        //空结点返回偷的结果集均为0，啥也没有
        if (root==null){
            return new int[]{0,0};
        }

        //左孩子偷不偷获益情况
        int[] leftDfs=dfs(root.left);
        //右孩子偷不偷获益情况
        int[] rightDfs=dfs(root.right);

        int[] curr=new int[2];
        //当前结点不偷
        curr[0]=Math.max(leftDfs[0],leftDfs[1])+Math.max(rightDfs[0],rightDfs[1]);
        //当前结点偷
        curr[1]=leftDfs[0]+rightDfs[0]+root.val;

        return curr;
    }
}