The idea is to work from bottom up, at each node return two values:

rob: maximum money we get from bottom of tree to the current node, if rob the current node noRob: maximum money we get from bottom of tree to the current node, if do not rob the current node==>1. rob = noRob_l + noRob_r + val(current node) <-- you rob current node, so can only use noRob value from both children (i.e. you cannot rob both children nodes in this case)

==>2. noRob = max(rob_l, noRob_l) + max(rob_r, noRob_r) <-- you do not rob current node, so can use either rob or noRob value from both children (you can rob both children nodes if you want in this case - so choose the larger between rob & noRob for both children)

The return value of recursion is a Node, containing the rob and noRob value for the current node.

class Solution { public: int rob(TreeNode* root) { Node ret = dfs(root); return max(ret.rob,ret.noRob); } private: struct Node { int rob, noRob; Node(int rob_, int noRob_):rob(rob_), noRob(noRob_) {} }; Node dfs(TreeNode* root) { if(!root) return Node(0,0); Node left = dfs(root->left); Node right = dfs(root->right); int rob = left.noRob + right.noRob + root->val; int noRob = max(left.rob, left.noRob) + max(right.rob,right.noRob); return Node(rob,noRob); } };