动态规划(六)--打家劫舍III (二叉树版)
来源：LeetCode
难度：中等
描述：
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例1：
示例2：
题外话：继偷完一维数组和环形数组，咱们又要尝试偷一把二叉树了...，实在没想到小偷行业也这么卷
分析：题意就是给一颗二叉树，让咱们在不能同时选择相邻节点的情况下找到整棵树和的最大值，这里的相邻节点即为父子节点，每个节点咱们都可以选择偷或者不偷，假设咱们选择父节点，那么两个子节点就不能选，但是可以选孙子节点，根据这个特性，咱们可以得出如下两种解法
解题
方法一：递归法
思路：由分析可知，咱们选了父节点，两个子节点就无法选择，但是可以选择孙子节点，所以该父节点当前能得到的最大值就是 父节点+孙子节点的值 VS 两个子节点值相加 中较大的那个，那么咱们采用递归方式遍历每个父节点的最大值即可
代码：
1public int rob(TreeNode root) {
2 if (root == null) {
3 return 0;
4 }
5 //该节点值
6 int money = root.val;
7 if (root.left != null) {
8 //左边两个孙子节点
9 money += (rob(root.left.left) + rob(root.left.right));
10 }
11
12 if (root.right != null) {
13 //右边两个孙子节点
14 money += (rob(root.right.left) + rob(root.right.right));
15 }
16 //该节点值 = Math.max(该节点值+4个孙子节点值，两个儿子节点值）
17 return Math.max(money, rob(root.left) + rob(root.right));
18 }
上面的代码很容易看出，递归的过程中咱们出现了大量的重复计算，如咱们计算每个节点的过程中，会把儿子及孙子节点都计算了，那么当儿子节点作为根节点时，又会计算到孙子节点...
所以咱们可以通过用Map存储每个节点结果的方式来进行优化，这个就不实现了，有兴趣的同学可以自己实现
题外话：可算逮着个机会偷懒了
方法二：动态规划
思路：如分析所说，咱们每个节点可以选择偷或者不透，所以我们每个节点结果有如下两种情况
当前节点选择不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
当前节点选择偷：当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
这里咱们用数组来每个节点保存偷和不偷的结果，0代表当前节点偷，1代表当前节点不偷
代码：
1public int rob(TreeNode root) {
2 int[] res = robDp(root);
3 return Math.max(res[0], res[1]);
4}
5
6public int[] robDp(TreeNode root) {
7 if (root == null) {
8 //节点为空，返回为0空数组
9 return new int[2];
10 }
11 int[] dp = new int[2];
12
13 //左右孩子能偷到的钱数
14 int[] leftDp = robDp(root.left);
15 int[] rightDp = robDp(root.right);
16
17 //当前节点偷 = 当前节点值 + 左右节点不偷值
18 dp[0] = root.val + leftDp[1] + rightDp[1];
19 //当前节点不偷 = 左右节点的最大值之和
20 dp[1] = Math.max(leftDp[0], leftDp[1]) + Math.max(rightDp[0], rightDp[1]);
21 return dp;
22}
题外话：偷完二叉树，下一次可能要求咱们去偷 图 类型的房子了...
以上仅是个人思路解法，觉得还不错欢迎点赞关注分享
往期精彩推荐