算法-动态规划-打家劫舍3

1 题目概述

1.1 题目出处

https://leetcode-cn.com/problems/house-robber-iii

1.2 题目描述

在这里插入图片描述

2 动态规划

2.1 思路

见代码注释。

2.2 代码

/** * 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) { 
        if(root == null){ 
            return 0;
        }
        // 需要分别考虑选本节点和不选本节点的两种情况
        // 选本节点时，最大金额取决于本节点金额加上不选左右子节点的最大金额
        // 而不选本节点时，最大金额计算就比较麻烦了，不一定选左右子节点就是最大金额
        // 所以这里必须要使用一个数组，分别记录选当前节点时的最大金额以及不选当前节点时的最大金额
        // 元素0代表选择本节点时的最大金额，元素1代表不选本节点时的最大金额
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }
    private int[] dfs(TreeNode root){ 
        // 元素0代表选择本节点时的最大金额，元素1代表不选本节点时的最大金额
        int[] result = new int[2];
        if(root == null){ 
            result[0] = 0;
            result[1] = 0;
            return result;
        }
        int[] l = dfs(root.left);
        int[] r = dfs(root.right);
        // 选择root时，最大金额就是root.val + 不选左右子节点时的最大金额
        result[0] = root.val + l[1] + r[1];
        // 而不选root时，最大金额为 Math.max(不选左子节点最大金额，选左子节点最大金额) 
        // + Math.max(不选右子节点最大金额，选右子节点最大金额)
        // 考虑 [4,1,null,2,null,3]这样的左斜二叉树，
        // 最大金额为7，就是直接选根节点4和尾节点3的和，跳过中间1和2
        // 而不是说选了4就必须选2才是最大！！！
        // 注意这和打家劫舍1和2中不同，那里面dp[i]表示选或不选i时的最大金额
        // 而这里的i节点的l[0]就表示包含了i节点值的最大金额了
        // 所以必须分开考虑！
        result[1] = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return result;
    }
}