# C++, JAVA, PYTHON & explanation

• Let

`f1(node)` be the value of maximum money we can rob from the subtree with `node` as root ( we can rob `node` if necessary).

`f2(node)` be the value of maximum money we can rob from the subtree with `node` as root but without robbing `node`.

Then we have

`f2(node) = f1(node.left) + f1(node.right)` and

`f1(node) = max( f2(node.left)+f2(node.right)+node.value, f2(node) )`.

# C++

``````class Solution {
public:
int rob(TreeNode* root) {
return robDFS(root).second;
}
pair<int, int> robDFS(TreeNode* node){
if( !node) return make_pair(0,0);
auto l = robDFS(node->left);
auto r = robDFS(node->right);
int f2 = l.second + r.second;
int f1 = max(f2, l.first + r.first + node->val);
return make_pair(f2, f1);
}
};
``````

# JAVA

``````public class Solution {
public int rob(TreeNode root) {
return robDFS(root)[1];
}
int[] robDFS(TreeNode node){
int [] res = new int[2];
if(node==null) return res;
int [] l = robDFS(node.left);
int [] r = robDFS(node.right);
res[0] = l[1] + r[1];
res[1] = Math.max(res[0], l[0] + r[0] + node.val);
return res;
}
}
``````

# PYTHON

``````class Solution(object):
def rob(self, root):
return self.robDFS(root)[1];
def robDFS(self,node):
if node is None:
return (0,0)
l = self.robDFS(node.left)
r = self.robDFS(node.right)
return (l[1] + r[1], max(l[1] + r[1], l[0] + r[0] + node.val))``````

• Using DFS is quite easy, but is it possible to use BFS to solve this problem ?

• Elegant solution.

• Just as easy as DFS. Just keep the larger of the sums of even and odd rows.

• Will not work that way when sum of your odd row with an even row which are not immediately connected becomes maximum.

• yeah you're right it will not work.

• Awesome Python solution!

• The key point is return two parameters with DFS. For each node: its either you rob it or not; if you rob it, you can't rob its left or right. It is similar to this one: https://leetcode.com/discuss/93387/line-python-solution-return-subtree-money-node-subtree-money

Your explanation for the algorithm is more clear but his explanation for code is more straightforward (personal opinion).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.