代码随想录算法训练营第三十九天-动态规划-337. 打家劫舍 III

• 老师讲这是树形dp的入门题目
• 解题思路是以二叉树的遍历（递归三部曲）再结合动规五部曲
• dp数组如何定义：只需要定义一个二个元素的数组，dp[0]与dp[1]
  • dp[0]表示不偷当前节点的最大价值
  • dp[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 {
private:int* binaryTreeRob(TreeNode* node) {if (node == nullptr) {return new int[2] {0, 0};}int* parr = new int[2] {0, 0};int* p_left = binaryTreeRob(node->left);int* p_right = binaryTreeRob(node->right);parr[1] = node->val + p_left[0] + p_right[0];parr[0] = std::max(p_left[0], p_left[1]) + std::max(p_right[0], p_right[1]);return parr;}
public:int rob(TreeNode* root) {int* arr = binaryTreeRob(root);return std::max(arr[0], arr[1]);}
};

• 这种题能有这种解法，非常敬佩
• 汇总