参考leetcode 336题打家劫舍3：
image.png
其实为了表示总共能得到的价值总和
一、dp的逻辑：
(0) 对于每个节点，有两种选择，即（选 , 不选）
(1) 选：那么它的素有子节点就不能选择，很好表达，即选 + 所有子节点不选
(2) 不选：注意，不代表着一定会选子节点，也就是对每个子节点有选与不选的自由，我们对每个子节点选最大的那种情况，也即max{子节点(选，不选）}
(3) 初始：也就是到达尾部，左右指针都是null，这个就是选=self.val, 不选=0
二、dfs：
这个就不用多说了，dfs + 上面的dp数据结构，给每个节点递归构造，最后得到根节点3的dp结果，取选与不选中的最大值即可
上代码：
class Solution {
public:
pair<int, int> returnTuple(TreeNode* &root){
if (root == nullptr) return {0,0};
auto l = returnTuple(root->left);
auto r = returnTuple(root->right);
int choose = root->val + l.second + r.second;
int not_choose = max(l.first, l.second) + max(r.first, r.second);
return make_pair(choose, not_choose);
}
int rob(TreeNode* root) {
auto ans = returnTuple(root);
return ans.first > ans.second?ans.first:ans.second;
}
};
