题目：

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

---

思路：

该题采用递归加动态规划的思想解决。
分析该题得到在结点i的位置需要计算它的孙子结点的最大值加上i结点本身的值。以及i结点左右孩子结点的最大值。设置一个数组名为rob，数组的长度为2。第一个值表示存储该结点。第二个值表示不存储该结点。因此状态方程为：

rob[0] = 该结点值 + 左结点不存储当前结点的值 + 右结点不存储当前结点的值
rob[1] = 右结点最大值 （存储当前结点和未存储当前结点中的最大值）+ 左结点最大值

---

代码：

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