C++, JAVA, PYTHON & explanation


  • 22
    C

    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))

  • 0
    L

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


  • 0
    S

    Elegant solution.


  • 0
    Q

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


  • 0
    N

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


  • 0
    Q

    yeah you're right it will not work.


  • 0
    K

    Awesome Python solution!


  • 0
    W

    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).


Log in to reply
 

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