337. House Robber III – Leetcode Solutions

Example 1:

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        
        # Helper function to return a tuple (rob, not_rob)
        # rob: max money we can get by robbing the current node
        # not_rob: max money we can get without robbing the current node
        def helper(node):
            if not node:
                # Base case: if the node is None, no money can be robbed
                return (0, 0)
            
            # Recursively calculate for left and right children
            left = helper(node.left)
            right = helper(node.right)
            
            # If we rob the current node, we cannot rob its direct children
            rob_current = node.val + left[1] + right[1]
            
            # If we don't rob the current node, we take the maximum money we can get from its children
            not_rob_current = max(left) + max(right)
            
            # Return both values: (rob_current, not_rob_current)
            return (rob_current, not_rob_current)
        
        # Start the recursive function from the root
        result = helper(root)
        
        # The result is the maximum between robbing or not robbing the root
        return max(result)

class Solution {
public:
    // Helper function to return a pair of values {rob, notRob}
    pair<int, int> helper(TreeNode* node) {
        // Base case: If the node is null, both rob and notRob are 0
        if (node == nullptr) {
            return {0, 0};
        }

        // Recurse for left and right children
        pair<int, int> left = helper(node->left);
        pair<int, int> right = helper(node->right);

        // If we rob this node, we cannot rob its children
        int rob = node->val + left.second + right.second;

        // If we do not rob this node, we take the maximum value of robbing or not robbing its children
        int notRob = max(left.first, left.second) + max(right.first, right.second);

        // Return the result as {rob, notRob}
        return {rob, notRob};
    }

    // Main function to calculate the maximum money the thief can rob
    int rob(TreeNode* root) {
        // Get the result from the helper function for the root node
        pair<int, int> result = helper(root);

        // Return the maximum of robbing or not robbing the root node
        return max(result.first, result.second);
    }
};

var rob = function(root) {
    // Helper function to perform DFS and return two results:
    // 1. Max money if the current node is robbed
    // 2. Max money if the current node is not robbed
    function dfs(node) {
        // Base case: If the node is null, return [0, 0] (robbed, not robbed)
        if (node === null) {
            return [0, 0];
        }
        
        // Recursively get the results from the left and right child nodes
        const left = dfs(node.left);
        const right = dfs(node.right);
        
        // If we rob the current house, we cannot rob the child houses
        const robCurrent = node.val + left[1] + right[1];
        
        // If we don't rob the current house, we can rob or not rob the child houses
        // So we take the maximum of robbing or not robbing for each child
        const skipCurrent = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        
        // Return an array where:
        // - First element is the max money if we rob the current node
        // - Second element is the max money if we don't rob the current node
        return [robCurrent, skipCurrent];
    }
    
    // Start the DFS traversal from the root and return the maximum possible value
    const result = dfs(root);
    
    // The maximum money the thief can rob is the larger of the two options
    return Math.max(result[0], result[1]);
};

class Solution {
    
    // Helper function that returns an array of two values:
    // - result[0]: maximum money we can rob if we do NOT rob this house
    // - result[1]: maximum money we can rob if we DO rob this house
    private int[] robHelper(TreeNode node) {
        // Base case: if the node is null, return [0, 0]
        if (node == null) {
            return new int[2];
        }
        
        // Recursively call the helper for the left and right subtrees
        int[] left = robHelper(node.left);
        int[] right = robHelper(node.right);
        
        // If we rob this house (node), we cannot rob the left and right children.
        // Hence, we take the current node's value and add the "no-rob" values of its children.
        int robThisHouse = node.val + left[0] + right[0];
        
        // If we do NOT rob this house, we can choose to either rob or not rob its children independently.
        // Hence, we take the maximum value of robbing or not robbing each child.
        int doNotRobThisHouse = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        
        // Return the result as an array of two elements.
        return new int[]{doNotRobThisHouse, robThisHouse};
    }
    
    public int rob(TreeNode root) {
        // Get the result from the helper function for the root node.
        int[] result = robHelper(root);
        
        // The final result is the maximum of robbing or not robbing the root house.
        return Math.max(result[0], result[1]);
    }
}