打家劫舍III
动态规划
返回数组就是dp数组。
- 下标为0记录：不偷该节点所得到的的最大金钱
- 下标为1记录：偷该节点所得到的的最大金钱。
在遍历的过程中，如果遇到空节点的话，无论偷还是不偷都是0，
首先明确的是使用后序遍历。 因为通过递归函数的返回值来做下一步计算。
- 通过递归左节点，得到左节点偷与不偷的金钱。
- 通过递归右节点，得到右节点偷与不偷的金钱。
单层递归的逻辑
- 如果是偷当前节点，那么左右孩子就不能偷，
val1 = cur->val + left[0] + right[0]; （ - 如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的
val2 = max(left[0], left[1]) + max(right[0], right[1]);
最后当前节点的状态就是{val2, val1};
即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}
/** * 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: //返回数组。0是不偷，1是偷 vector<int> backtracking(TreeNode* cur) { //空节点，偷和不偷都是0 if(cur == nullptr )return vector<int>(2,0); vector<int> left = backtracking(cur->left); vector<int> right = backtracking(cur->right); //不偷，在左右子节点选最大的 int val0 = max(left[0],left[1]) + max(right[0] , right[1]); //偷，当前节点加上左右不偷 int val1 = cur->val + left[0] + right[0]; return vector<int>{val0 ,val1}; } int rob(TreeNode* root) { vector<int> result = backtracking(root); //偷和不偷选最大 return max(result[0],result[1]); } };
二刷（回溯）
/** * 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: int result = 0; unordered_map<TreeNode* , int> my_map; int trak_back(TreeNode* cur) { if(cur == nullptr) return 0; if(my_map[cur] != 0) return my_map[cur]; else if(cur->left==nullptr && cur->right==nullptr) return cur->val; int value = cur->val; if(cur->left != nullptr ) value += trak_back(cur->left->left) + trak_back(cur->left->right); if(cur->right != nullptr ) value += trak_back(cur->right->left) + trak_back(cur->right->right); my_map[cur] = max( value , trak_back(cur->left) + trak_back(cur->right)); return my_map[cur]; } int rob(TreeNode* root) { return trak_back(root); } };
二刷（树形递归）
/** * 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: vector<int> track_back(TreeNode* cur) { if(cur == nullptr) return {0,0}; vector<int> dp(2,0); vector<int> left_dp = track_back(cur->left); vector<int> right_dp = track_back(cur->right); //不偷当前节点，左右节点可偷可不偷，选大的 dp[0] = max(left_dp[0],left_dp[1]) + max(right_dp[0],right_dp[1]); //偷当前节点 dp[1] = cur->val + left_dp[0] + right_dp[0]; return dp; } int rob(TreeNode* root) { //dp[0]为当前节点不偷的值，dp[1]为偷 vector<int> dp = track_back(root); return max(dp[0] , dp[1]); } };
