CONY的世界

337. 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.

這題並不是odd, even depth 取最大就可以解的

因為有這種例子 ex.[4,1,null,2,null,3,null] 一直線的，但是最大值不是出現在奇偶數間隔最大值，而是出現在相隔為2的 4+3

看到這個例子應該就知道要用dp了

所以要思考的是怎麼列出dp 算式，基本上就是看take 或 not_take，所以每個node會有兩個值，從底層開始累積上去 （也就是用recursion)

要注意的是not_take(n) 是取 max( not_take(n-1), take(n-1)) ，因為世上是這樣你不取n不代表你一定要take(n-1），你還是可以 not_take(n-1)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] res=robSub(root);
        return Math.max(res[0],res[1]);
    }
    private int[] robSub(TreeNode node) {
        if(node == null)    return new int[2];
        
        int[] left = robSub(node.left);
        int[] right = robSub(node.right);
        
        int[] res = new int[2];
        res[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        res[1] = node.val+left[0]+right[0];
        return res;
    }
}