Tree DP: House Robber III and Tree Optimization

House Robber III (LeetCode 337)

The binary tree version: you cannot select adjacent (parent-child) nodes. Find the maximum value.

Strategy: Post-order Traversal (DFS + DP). Each node returns a 2nd-order array: [Max if NOT robbing this node, Max if ROBBING this node].

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

private int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    
    int[] left = dfs(node.left);
    int[] right = dfs(node.right);
    
    // Case 1: NOT robbing current node
    // Maximize left and right subtrees independently (can either rob or not rob children)
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    
    // Case 2: ROBBING current node
    // Must NOT rob direct children (must take their left[0] and right[0])
    int rob = node.val + left[0] + right[0];
    
    return new int[]{notRob, rob};
}

Binary Tree Cameras (LeetCode 968)

Minimum cameras needed to monitor all nodes. A camera covers its parent, itself, and its children.

Strategy: Greedy DFS. Use states to communicate coverage status upwards:

• 0: Node is uncovered (needs its parent to install a camera).
• 1: Node is covered but has no camera.
• 2: Node has a camera.

int cameraCount = 0;

public int minCameraCover(TreeNode root) {
    // If root remains uncovered by its children, it MUST have a camera
    return dfs(root) == 0 ? cameraCount + 1 : cameraCount;
}

private int dfs(TreeNode node) {
    if (node == null) return 1; // Null nodes are "covered" by default
    
    int left = dfs(node.left);
    int right = dfs(node.right);
    
    // If any child is uncovered, parent MUST install a camera
    if (left == 0 || right == 0) {
        cameraCount++;
        return 2;
    }
    
    // If any child has a camera, current node is "covered"
    if (left == 2 || right == 2) {
        return 1;
    }
    
    // If children are covered but have no cameras, current node is "uncovered"
    return 0;
}

Binary Tree Maximum Path Sum (LeetCode 124)

Find the non-empty path with the largest sum. The path can start and end at any node.

int globalMax = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    calculateContribution(root);
    return globalMax;
}

// Returns the maximum contribution from a single path starting at this node
private int calculateContribution(TreeNode node) {
    if (node == null) return 0;
    
    // Negative contributions are ignored (capped at 0)
    int leftMax = Math.max(calculateContribution(node.left), 0);
    int rightMax = Math.max(calculateContribution(node.right), 0);
    
    // Update global max considering the path spanning through current node
    globalMax = Math.max(globalMax, node.val + leftMax + rightMax);
    
    // For recursion up the tree, we can only pick ONE branch to continue the path
    return node.val + Math.max(leftMax, rightMax);
}

Summary Selection Guide