337. 打家劫舍 III（dfs）
链接337. 打家劫舍 III - 力扣LeetCode题解代码1.打劫当前节点root-val left和right不打劫的最大值2.不打劫当前节点left打劫和不打劫的最大值right打劫和不打劫的最大值/** * 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: struct Result { int yes_result; int no_result; Result() { yes_result 0; no_result 0; } }; int rob(TreeNode* root) { if (!root) { return 0; } Result res dfs(root); return max(res.yes_result, res.no_result); } Result dfs(TreeNode* root) { if (!root) { Result tmp; return tmp; } Result left dfs(root-left); Result right dfs(root-right); Result res; res.yes_result root-val left.no_result right.no_result; res.no_result max(left.yes_result, left.no_result) max(right.yes_result, right.no_result); return res; } };/** * * Definition for a binary tree node. * * struct TreeNode { * * int val; * * TreeNode *left; * * TreeNode *right; * * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * * }; * */ class Solution { public: std::unordered_mapTreeNode*, int table; int rob(TreeNode* root) { if(!root) { return 0; } // 记忆化搜索 if(table.find(root) ! table.end()) { return table[root]; } // max2是不包含root的最大值 int left rob(root-left); int right rob(root-right); int max2 left right; // max1是包含root的最大值 int max1 root-val; if(root-left) { max1 rob(root-left-left) rob(root-left-right); } if(root-right) { max1 rob(root-right-left) rob(root-right-right); } // 记录以root为根的最大值 table[root] max(max2, max1); return table[root]; } };
