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.



不直接连接的nodes
什么是直接连接：parent-children 是直接连接。
因此只需要不是parent-children 关系的都可以加起来。
对root 来说，不直接连接的是grandchildren。 我们计算完root后还需要知道root.left + root.right的结果
因此对于一个node来说有两种选择，take or not

 public int rob(TreeNode root) {  
     int[] ans = helper(root);  
     return Math.max(ans[0],ans[1]);  
   }  
   public int[] helper(TreeNode root){  
     int[] ans = new int[2];  
     if(root == null) return ans;  
     int[] left=helper(root.left);  
     int[] right=helper(root.right);  
     //max sum take this level  
     ans[0] = Math.max(left[1]+right[1]+root.val, root.val);  
     //max sum not take this level   
     ans[1] = Math.max(left[0] + right[1],
                   Math.max(left[1] + right[0], 
                        Math.max(left[0] + right[0], left[1]+right[1])));  
     return ans ;  
   }  

改进：

    ans[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);