- 老师讲这是树形
dp的入门题目 - 解题思路是以二叉树的遍历（递归三部曲）再结合动规五部曲
dp数组如何定义：只需要定义一个二个元素的数组，dp[0]与dp[1] dp[0]表示不偷当前节点的最大价值dp[1]表示偷当前节点后的最大价值- 这样可以把每个节点的状态值都表示出来
- 但这个数组的两个值只表示当前节点的状态值
- 递归时要使用后序遍历：
- 使用后序遍历的原因就是要从叶子结点一层一层向上统计出来
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]);}
};
