Leetcode House Robber III problem solution

In this Leetcode House Robber III problem solution, The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night. we have given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Leetcode House Robber III problem solution in Python.

class Solution:
    
    import functools
    
    @functools.lru_cache(maxsize=200)
    def rob(self, root: TreeNode) -> int:
        if not root:
            return 0
        #case 1
        res1 = root.val
        if root.left and root.left.left:
            res1 += self.rob(root.left.left)
        if root.left and root.left.right:
            res1 += self.rob(root.left.right)
        if root.right and root.right.left:
            res1 += self.rob(root.right.left)
        if root.right and root.right.right:
            res1 += self.rob(root.right.right)
        res2 = self.rob(root.left) + self.rob(root.right)
        
        return max(res1, res2)

House Robber III problem solution in Java.

class Solution {
    public int rob(TreeNode root) {
        return dfs(root, true);
    }
    
    public int dfs(TreeNode root, boolean canRob){
        if(null==root)return 0;
        if(canRob){
            int rob = dfs(root.left, false)+root.val+dfs(root.right, false);
            int nrob = dfs(root, false);
            return Math.max(rob, nrob);
        }
        return dfs(root.left, true)+dfs(root.right, true);
    }
}

Problem solution in C++.

class Solution {
public:
    int rob(TreeNode* root) {
        unordered_map<TreeNode*, int> dict;
        return help(root, dict);
    }
    
    int help(TreeNode* root, unordered_map<TreeNode*, int>& dict) {
        if(root == NULL)  return 0;
        if(dict.find(root)!=dict.end())  return dict[root];
        int val = 0;
        if(root->left != NULL) {
            val += help(root->left->left, dict) + help(root->left->right, dict);
        }
        if(root->right != NULL) {
            val += help(root->right->left, dict) + help(root->right->right, dict);
        }
        val = max(val + root->val, help(root->left, dict) + help(root->right, dict));
        dict[root] = val;
        return val;
    }
};

Problem solution in C.

int max(int a,int b)
 {
     return (a>b?a:b);
 }
 struct node
 {
     int dd[2];
     struct node *left,*right;
 };
 int gans(struct TreeNode* root,int f,struct node **x)
 {
        if (root==NULL)
        return 0;
        int ret;
        if (*x!=NULL&&(*x)->dd[f]!=-1)
        {
            return (*x)->dd[f];
        }
        if (*x==NULL)
        {
            *x=(struct node *)malloc(sizeof(struct node ));
            (*x)->left=(*x)->right=NULL;
            (*x)->dd[0]=(*x)->dd[1]=-1;
        }
        if (f)
        {
            ret= max(root->val+gans(root->left,!f,&((*x)->left))+gans(root->right,!f,&((*x)->right)),gans(root->left,1,&((*x)->left))+gans(root->right,1,&((*x)->right)));
        }
        else 
        {
            ret= gans(root->left,!f,&((*x)->left))+gans(root->right,!f,&((*x)->right));
        }
       
        (*x)->dd[f]=ret;
        
        return ret;
 }
int rob(struct TreeNode* root) {
    struct node *x=NULL;
    int p2=gans(root,1,&x);
    return p2;
    
}

Leetcode House Robber III problem solution

Leetcode House Robber III problem solution in Python.

House Robber III problem solution in Java.

Problem solution in C++.

Problem solution in C.

Leave a Reply

Pages

Practice