337. 打家劫舍 III

这是一道树形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:int rob(TreeNode* root) {vector<int> result = DP(root);//从根节点开始dpreturn max(result[0], result[1]);}vector<int> DP(TreeNode* node) {vector<int> l(2), r(2);//两个小数组，l为左结点，r为右结点if (node->left)l = DP(node->left);  //递归到return一个vector数组if (node->right)r = DP(node->right);//后序遍历int v1 = node->val + l[1] + r[1];//选当前结点，则该结点的值加上不选左右结点的值int v2 = max(l[0], l[1]) + max(r[1], r[0]);//不选当前结点，则分别判断左右结点，算它们各自选或不选的最大值return {v1, v2};//返回vector数组，下标0为选该结点的值，下标1为不选该结点的值}
};