```
/**
* 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) {
int withRoot;
int withoutRoot;
robHelper(root, withRoot, withoutRoot);
return max(withRoot, withoutRoot);
}
void robHelper(TreeNode* root, int& withRoot, int& withoutRoot)
{
if(!root)
{
withRoot = 0;
withoutRoot = 0;
return;
}
int withRootL;
int withoutRootL;
robHelper(root->left, withRootL, withoutRootL);
int withRootR;
int withoutRootR;
robHelper(root->right, withRootR, withoutRootR);
withRoot = root->val + withoutRootL + withoutRootR;
withoutRoot = max(withRootL, withoutRootL) + max(withRootR, withoutRootR);
}
};
```