打家劫舍III

题目描述

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

题目链接：https://leetcode.cn/problems/house-robber-iii/

文章讲解：https://programmercarl.com/0337.打家劫舍III.html

思路

首次遇见树形 dp ！也不奇怪，数组的dp见过了 树形的dp也很正常，只要熟练掌握树的遍历就可以。

本质上都是线性结果嘛。

那么用什么遍历顺序？因为我们需要累计金额，因此需要函数返回值来接住。也可以理解为金额是一个伴随着节点变化的值。

当前节点偷还是不偷？

如果偷了当前节点，两个孩子就不能动，如果没偷当前节点，就可以考虑偷左右孩子（注意这里说的是“考虑”）

每个节点依然是偷与不偷两个状态，因此仍然是一个决策树，并且要求最大金额这个最优化描述，可以尝试动态规划。

定义每个节点的状态，偷和不偷，偷的累计最大金额是多少，不偷的累计最大金额是多少？

这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。

在树上进行状态转移

写的时候既要递归三部曲写出遍历，又要动规五部曲融入动规逻辑。

1、确定递归参数和返回值

一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。

dp数组及下标含义：数组第一个元素记录不偷该节点所得到的的最大金钱，第二个元素记录偷该节点所得到的的最大金钱。

2、终止条件

空节点返回数组[0，0]，表明当前节点偷不偷，得到的金钱都是0。

3、遍历顺序。

后序遍历。子房间偷盗的前要“上交”给父房间

递归左节点，得到左节点偷与不偷得到的金钱

递归右节点，得到右节点偷与不偷得到的金钱

4、单层递归逻辑

之前说了如果偷了当前节点，两个孩子就不能动；值就是当前节点值+左节点没被偷+右节点没被偷

如果没抢当前节点，就可以考虑偷左右孩子（注意这里说的是“考虑”）；既然孩子可偷也可不偷，那么一定要选个最大值。选择左节点可偷可不偷的最大值，再选择右节点可偷可不偷的最大值，最后相加便是两个节点可偷可不偷的最大值。

注意，我们将空节点也视为一个真正的节点。

以示例1为例，dp数组状态如下：（注意用后序遍历的方式推导）

最后头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱。

代码实现

vector<int> traversal(TreeNode* node){
    if(node == nullptr) return vector<int>{0,0};
    vector<int> left = traversal(node->left);
    vector<int> right = traversal(node->right);
    int value1 = node->val + left[0] + right[0];
    int value2 = max(left[0],left[1]) + max(right[0],right[1]);
    return {value2,value1};
}

int rob(TreeNode* root) {
    vector<int> dp = traversal(root);
    return max(dp[0],dp[1]);
}