Untitled

 avatar
unknown
plain_text
a month ago
1.0 kB
2
Indexable
// pick not pick pattern
// include exclude pattern
// take not take pattern

public class HouseRobberIII {

    public int rob(TreeNode root) {
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }

    // Returns an array where:
    // result[0] = max amount when  robbing the current node
    // result[1] = max amount when not robbing the current node
    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }

        // Post-order traversal: process left and right children first
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        // If we rob the current node, we cannot rob its children
        int robCurrent = node.val + left[1] + right[1];

        // If we do not rob the current node, we take the max from children
        int notRobCurrent = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return new int[]{robCurrent, notRobCurrent};
    }
Leave a Comment