链接：https://leetcode.cn/problems/house-robber-iii/solution/by-xun-ge-v-x6f0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。?
题目
?
示例
?
思路
- 确定递归函数的参数和返回值
以下数组我们直接用结构体代替
这里我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。
所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
所以本题dp数组就是一个长度为2的数组！
那么有同学可能疑惑，长度为2的数组怎么标记树中每个节点的状态呢？
别忘了在递归的过程中，系统栈会保存每一层递归的参数。
如果还不理解的话，就接着往下看，看到代码就理解了哈。
- 确定终止条件
在遍历的过程中，如果遇到空间点的话，很明显，无论偷还是不偷都是0，所以就返回
if (cur == NULL) return {0, 0};
这也相当于dp数组的初始化
- 确定遍历顺序
首先明确的是使用后序遍历。因为通过递归函数的返回值来做下一步计算。
- 通过递归左节点，得到左节点偷与不偷的金钱。
- 通过递归右节点，得到右节点偷与不偷的金钱。
代码如下：
// 下标0：不偷，下标1：偷
left = robTree(cur->left); // 左
right = robTree(cur->right); // 右
// 中
- 确定单层递归的逻辑
如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果对下标含义不理解就在回顾一下dp数组的含义）
如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/* 记录节点最高金额 */
struct status {
int select;
int notselect;
};
struct status dfs(struct TreeNode* root) {
/* 节点为空，返回0 */
if (root == NULL) {
return (struct status){0, 0};
}
/* 依次遍历左右子树 */
struct status l = dfs(root->left);
struct status r = dfs(root->right);
/* 选择当前节点所得金额 */
int select = root->val + l.notselect + r.notselect;
/* 不选择当前节点所得金额 */
int notselect = fmax(l.select, l.notselect) + fmax(r.select, r.notselect);
/* 返回当前节点两种所得金额 */
return (struct status){select, notselect};
}
/*
*int rob(struct TreeNode* root)
int rob：求树节点总和最大值，不能同时选择父子节点
struct TreeNode* root：树的头结点
返回值：总和最大值
*/
int rob(struct TreeNode* root){
/* 对树从根节点进行dfs搜索 */
struct status root_status = dfs(root);
/* 比较根节点选或不选所得分数，取较大值 */
return fmax(root_status.select, root_status.notselect);
}
作者：xun-ge-v
链接：https://leetcode.cn/problems/house-robber-iii/solution/by-xun-ge-v-x6f0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。