题目：

337. 打家劫舍 III
在这里插入图片描述

题解：动态规划

在这里插入图片描述

1. 解释一：

在这里插入图片描述

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

2. 解释二：

在这里插入图片描述

3. 解释三：

在这里插入图片描述

代码：动态规划

public class code337 { 
    // 树的后序遍历
    public static int rob(TreeNode root) { 
        // 计算当前节点偷与不偷所能获得收益，结果存在数组res中
        int res[] = dfs(root);
        // 根据题意可知需取其中最大的
        return Math.max(res[0], res[1]);
    }
    public static int[] dfs(TreeNode root)
    { 
        // 如果当前节点为空节点，则其结果为0
        if(root == null)
        { 
            int temp[] = {  0, 0 };
            return temp;
        }
        // 分类讨论的标准是：当前结点偷或者不偷
        // 由于需要后序遍历，所以先计算左右子结点，然后计算当前结点的状态值
        // 计算当前节点左儿子偷与不偷所能获得的收益
        int left[] = dfs(root.left);
        // 计算当前节点右儿子偷与不偷所能获得的收益
        int right[] = dfs(root.right);
        // dp[0]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点不偷
        // dp[1]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点偷
        int dp[] = new int[2];
        // 不偷，下家可偷可不偷，取决于收益大小
        // 不偷当前节点所能获得的最大收益 = 左儿子所能获得的最大收益 + 右儿子所能获得的最大收益
        // 儿子所能获得最大收益为：max（不偷当前儿子所能获得最大收益，偷当前儿子所能获得最大收益）
        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        // 偷，下家就不能偷了
        // 偷当前节点所能获得的最大收益= 偷当前节点的钱 + 不偷左儿子所获得的钱 +不偷右儿子所获得的钱
        dp[1] = root.val + left[0] + right[0];
        return dp;
    }
    public static void main(String[] args) { 
        Integer nums1[] = {  3, 2, 3, null, 3, null, 1 };
        TreeNode root1 = ConstructTree.constructTree(nums1);
        TreeOperation.show(root1);
        System.out.println("***************************************");
        int res1 = rob(root1);
        System.out.println(res1);
        System.out.println("***************************************");
        Integer nums2[] = {  3, 4, 5, 1, 3, null, 1 };
        TreeNode root2 = ConstructTree.constructTree(nums2);
        TreeOperation.show(root2);
        System.out.println("***************************************");
        int res2 = rob(root2);
        System.out.println(res2);
        System.out.println("***************************************");
        Integer nums3[] = {  2, 1, 3, null, 4 };
        TreeNode root3 = ConstructTree.constructTree(nums3);
        TreeOperation.show(root3);
        System.out.println("***************************************");
        int res3 = rob(root3);
        System.out.println(res3);
        System.out.println("***************************************");
    }
}