Cacher is the code snippet organizer for pro developers

/**
 * 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) {
        return dfs(root).first;
    }
    pair<int, int> dfs(TreeNode* root) {
        pair<int, int> dp = make_pair(0,0);
        if (root) {
            pair<int, int> dp_L = dfs(root->left);
            pair<int, int> dp_R = dfs(root->right);
            dp.second = dp_L.first + dp_R.first;
            dp.first = max(dp.second, dp_L.second+dp_R.second+root->val);
        }
        return dp;
    }
};