【树的DFS】个人练习-Leetcode-337. House Robber III

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

题目大意：基本与【打家劫舍I】相同，但房子的结构是树形的，限制是两个相邻节点不能同时偷。求最大值。

思路：DFS递归来做。对某一个节点node无非就是选或者不选。设f[node]为选了该节点，该节点及其子树的最大值；g[node]为不选该节点，该节点及其子树最大值。那么很明确答案就是max(f[root], g[root])。

接下来寻找转移关系。

• 如果一个节点被选取了，那么f[node] = node->val + g[node->left] + g[node->right]，这个值就是自身的值加上左右节点【不被选的值】
• 如果一个节点未必选取，那么g[node] = max(f[node->left], g[node->left]) + max(f[node->right], g[node->right])，此时左右节点可选也可不选，但一定有两个组成部分，即来自左边的和来自右边的。那么【左边取或者不取选最大】加上【右边取或者不取选最大】就是该节点的g值

【注意！】此时遍历应该是【后序遍历】，因为每一个父节点的f, g值只有当【左右儿子的f, g值都算出来后】才可以计算。叶子节点的f, g值计算很方便。我开始写的时候思路是对的，但没写成后序遍历，搞得超时了…

用map<TreeNode*, int>来保存从指针到数值的映射，并且给null地址直接赋0。感觉更多的是DFS，实际上和DP关系不大。

完整代码

/* Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:map<TreeNode*, int> f;map<TreeNode*, int> g;void DFS(TreeNode* node) {if (node == nullptr)return ;DFS(node->left);DFS(node->right);if (node->left == nullptr && node->right == nullptr) {f[node] = node->val;g[node] = 0;}else {f[node] = node->val + g[node->left] + g[node->right];g[node] = max(f[node->left], g[node->left]) + max(f[node->right], g[node->right]);}}int rob(TreeNode* root) {f[nullptr] = g[nullptr] = 0;DFS(root);return max(g[root], f[root]);}
};