337. House Robber III

House Robber III

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 1:

 3
/ \

2 3 \ \ 3 1

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

Example 2:

 3
/ \

4 5 / \ \ 1 3 1

Maximum amount of money the thief can rob = 4 + 5 = 9.

Credits:Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
     public int rob(TreeNode root) {
        int[] result = helper(root);
        return Math.max(result[0], result[1]);
    }

    private int[] helper(TreeNode node) {
        if (node == null) {
            int[] result = new int[2];
            return result;
        }

        int[] left = helper(node.left);
        int[] right = helper(node.right);

        int[] result = new int[2];
        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        result[1] = node.val + left[0] + right[0];
        return result;
    }
}