337. House Robber III

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.

My Solutions:

两个相连的node不能同时rob，说明，只能每次隔一层rob一次，e.g. rob第一层，跳过第二层，rob第三层。。。

因此一个int[] res里有两个数，代表两种情况，第一个数是不rob此node，第二个数是rob此node获得的钱

对第一个数，因为没有rob这个node，可以直接相加left and right children的最大数

对第二个数，因为rob了这个node，所以res【2】是此node的val + 它的left和right的第一个数（不rob left or right children）

比如第一个例子，最后的结果是：

3 [3+2,3+3+1]

/ \

2[3,2] 3[1,3]

\ \

3[0,3] 1[0,1]

class Solution {  
      public int rob(TreeNode root) {
        int[] res = helper(root);
        return Math.max(res[0], res[1]);
    }
    
    private int[] helper(TreeNode root) {
        if (root == null) return new int[2];
        
        int[] left = helper(root.left);
        int[] right = helper(root.right);
        int[] res = new int[2];
        
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = root.val + left[0] + right[0];
        
        return res;
      }
}