[LeetCode] House Robber III

LeetCode House Robber III 

Problem:
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.

This is a Maximum Weight Independent Set Problem in disguise, which is NP-hard. However to find the max weight set in a tree is possible.

Given a node, if we use maxWith(node) denote the max weight with node in the set, maxWithout(node) denote the max weight without node in the set, max(node) is the max weight with the subtree rooted at node.

1. if node is in the solution, then maxWith(node) = sum of maxWithout(node.children) + node
2. if node is not in the solution, the maxWithout(node) = sum of max(node.child)

Then max(node) = max of maxWith(root), maxWithout(node)

This can be done using dynamic program to start the leaves first then go up to the tree to calculate the maxWithout() and max() for each node. To achieve this we use recursive post-order traversal.

	public class Solution {
	public int rob(TreeNode root) {
	Map<TreeNode, Integer> max = new HashMap<>();
	Map<TreeNode, Integer> maxWO = new HashMap<>();
	rec(root, max, maxWO);
	return max.get(root);
	}
	private void rec(TreeNode root, Map<TreeNode, Integer> max, Map<TreeNode, Integer> maxWO){
	if(root == null){
	max.put(root, 0);
	maxWO.put(root, 0);
	return;
	}
	rec(root.left, max, maxWO);
	rec(root.right, max, maxWO);
	//without root
	maxWO.put(root, (root.left==null?0:max.get(root.left)) + (root.right==null?0:max.get(root.right)));
	//with root
	int maxW = root.val + (root.left==null?0:maxWO.get(root.left)) + (root.right==null?0:maxWO.get(root.right));
	max.put(root, Math.max(maxW, maxWO.get(root)));
	}
	}

view raw houserobber3.java hosted with ❤ by GitHub