House Robber III

Rob the most amount of money.

Question

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example:

Input: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

Output: 7 
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Analyzation

1. This dp array is for calculating the maximum profit of a robber and it is a bottom-up(iterative) approach.

2. Initialization: If there is no house, return 0, if only one house, return that house’s profit, if two houses, choose the largest profit.

3. Transition Functions: We only need to recursively do either choose the path with root or not. Note that when choosing without root, we need to compare the left and right subtree’s “with its root” or not.

4. Result: return the results of either with root or not.

The Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /*
        Dynamic Programming
        
        Similar solution to House Robber II which either selects the root or not recursively
    */
    public int rob(TreeNode root) {
        if(root == null) {
            return 0;
        }
        
        int[] res = helper(root);
        
        return Math.max(res[0], res[1]);
    }
    
    public int[] helper(TreeNode root){
        
        // if the root is null, we set the result array as 0
        if(root == null){
            int[] result = {0,0};
            return result;
        }
        
        // hold left children or right children
        int[] result = new int[2];
        int[] left = helper(root.left);
        int[] right = helper(root.right);
        
        // result[0] takes root and only the grandchildren
        result[0] = root.val + left[1] + right[1];
        
        // result[1] takes the maximum profit of left children or left grandchilder
        // same as right side.
        result[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        
        return result;
    }
}

Time & Space Complexity

• Time Complexity: Since we have a recursion so it is O(n).
• Space Complexity: Since we create a dp array, the Space Complexity is O(n).