LeetCode 337: House Robber III Solution

Master LeetCode problem 337 (House Robber III), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

337. House Robber III

Medium

Dynamic Programming Tree Depth-First Search Binary Tree

Problem Explanation

Explanation

To solve this problem, we can use a recursive approach where we traverse the binary tree in a depth-first manner. For each node, we can either choose to rob the current node and skip the children, or skip the current node and rob the children. We need to keep track of the maximum amount of money the thief can rob without alerting the police.

We will define a helper function that returns an array of two elements. The first element represents the maximum amount of money that can be robbed if the current node is not robbed, and the second element represents the maximum amount if the current node is robbed.

At each node, we will calculate the maximum amount if the current node is not robbed as the maximum of the sums of the values returned by the children's nodes. And the maximum amount if the current node is robbed will be the sum of the value of the current node, and the values returned by the children's nodes if they are not robbed.

We will then return the maximum value between the two options for the current node.

Solution Code

class Solution {
    public int rob(TreeNode root) {
        int[] result = robSub(root);
        return Math.max(result[0], result[1]);
    }
    
    private int[] robSub(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }
        
        int[] left = robSub(node.left);
        int[] right = robSub(node.right);
        
        int[] result = new int[2];
        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        result[1] = node.val + left[0] + right[0];
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 337 (House Robber III)?

This page provides optimized solutions for LeetCode problem 337 (House Robber III) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 337 (House Robber III)?

The time complexity for LeetCode 337 (House Robber III) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 337 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 337 in Java, C++, or Python.

Back to LeetCode Solutions