春江花朝秋月夜
往往取酒还独倾
C++，动态规划+dfs。
这道题里其实也是一种动态规划的思想，而且很容易就能想到如何求解最优解。
每个结点对应两种状态，计算自己和不计算自己，也就是对应题意中的偷与不偷。
其中每种状态都能对应一个最优解，也就是二叉树中由下到上，考虑偷不偷本结点，得到能偷到的最大钱数。
需要注意的是：
- 如果考虑偷当前结点，则一定不能偷最近的左右儿子结点
- 如果不偷当前结点，则左右儿子结点可偷可不偷，根据能获得的最大钱数决定偷不偷
状态转移方程如下：
\[f(root) = h(root.left) + h(root.right) + root.val\] \[h(root) = max\{f(root.left), h(root.left\} + max\{f(root.right), h(root.right\}\]其中\(f(x) \)表示偷x结点，\(h(x) \)表示不偷x结点。
当然还有一个问题，就是动态规划要求先得到子问题的最优解。
对应本题也就是先解决子结点，才能解决父节点的问题，在二叉树中dfs似乎不太好做到这一点，毕竟不能从子节点回到父节点。
不过我们有后序遍历啊！！！后序遍历先得到左右子节点的解，再求解当前结点的最优解。
需要说明的是，可以在遍历每个结点的时候，用一个vector同时记录偷和不偷两种结果并返回，能减少很多计算量，否则会超时。
基于以上思路，就可以写出代码了。
/**
* 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:
int rob(TreeNode* root) {
vector<int> ans = dfs(root);
return max(ans[0], ans[1]);
}
vector<int> dfs(TreeNode *root) {
if (!root) return vector<int> (2, 0);
vector<int> left = dfs(root->left);
vector<int> right = dfs(root->right);
vector<int> ans(2);
ans[0] = left[1] + right[1] + root->val;
ans[1] = max(left[0], left[1]) + max(right[0], right[1]);
return ans;
}
};
