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.

Have you met this question in a real interview?

Yes

Example

  3
 / \
2   3
 \   \ 
  3   1

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

    3
   / \
  4   5
 / \   \ 
1   3   1

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

1. divide and conquer

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
class ReturnType {
    int includeMax = 0;
    int excludeMax = 0;
    public ReturnType(int includeMax, int excludeMax) {
        this.includeMax = includeMax;
        this.excludeMax = excludeMax;
    }
}

public class Solution {
    /*
     * @param root: The root of binary tree.
     * @return: The maximum amount of money you can rob tonight
     */
    //private int globalTotalMax = 0;
    public int houseRobber3(TreeNode root) {
        // write your code here
        if (root == null) {
            return 0;
        }

        ReturnType ans =  divideConquer(root);
        return Math.max(ans.includeMax, ans.excludeMax);
    }

    public ReturnType divideConquer(TreeNode root) {
        if (root == null) {
            return new ReturnType(0, 0);
        }

        ReturnType left = divideConquer(root.left);
        ReturnType right = divideConquer(root.right);

        int includeMax = root.val + left.excludeMax + right.excludeMax;

        int excludeMax = Math.max(left.includeMax, left.excludeMax) +
                         Math.max(right.includeMax, right.excludeMax);
        /*

        int a = Math.max((left.excludeMax + right.excludeMax), (left.includeMax + right.includeMax));
        int b = Math.max((left.excludeMax + right.includeMax), (left.includeMax + right.excludeMax));
        */
        return new ReturnType(includeMax, excludeMax);
    }
}

1. dp