LeetCode 337: House Robber III

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.

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;
    }
}