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:

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

Example 2:

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

乍一看，这个问题表现出了“最优子结构”的特征:如果我们想从当前的二叉树(根在根)中提取最大的钱数，我们当然希望我们可以对它的左右子树做同样的事情。
沿着这条线，让我们定义函数rob(根)它将返回我们可以抢夺根在根的二叉树的最大数量的钱;
现在的关键是，从解决问题的解决方案到其子问题的解决方案。
如何从rob(root.left)、rob(root.right)、rob(root.right)中获取rob(root)。
显然上面的分析提出了一个递归的解决方案。
对于递归，我们总是有必要弄清楚以下两个属性:

终止条件:什么时候我们不需要计算就知道了rob(root)的答案?
当然，当树是空的时候，我们没有什么东西要抢，所以钱的数量是零。
递归关系:即。
如何从rob(root.left)、rob(root.right)、rob(root.right)中获取rob(root)。
从树根的角度来看，最后只有两种情况:根被抢或不被抢。
如果是这样，由于“我们不能剥夺任何两个直接连接的房子”的约束，下一层次的子树将是四个“子树”(root.left)。
离开了,root.left。
root.right。
离开,root.right.right)。
但是，如果根没有被剥夺，可用子树的下一个级别就是两个“子树”(根)。
离开,root.right)。
我们只需要选择收益率更大的情况。

1 class Solution {
2     public int rob(TreeNode root) {
3         if(root==null) return 0;//终止条件
4         int res = 0;//当层的结果
5         if(root.left!=null) res +=rob(root.left.left)+rob(root.left.right);
6         if(root.right!=null) res +=rob(root.right.left)+rob(root.right.right);
7         return Math.max(res+root.val,rob(root.left)+rob(root.right));
8     }
9 }

在第一步中，我们将我们的问题定义为rob(root)，它将产生最大金额的钱，可以被剥夺根在根上的二叉树。

现在让我们回过头来问为什么我们有重叠的子问题。
如果你回溯到开始，你会发现答案就在我们定义罗伯(root)的方式上。
正如我前面提到的，对于每个树根，有两种情况:它是被抢的，或者不是。
rob(root)没有区分这两种情况，所以“随着递归的深入和深入，信息丢失了”，这导致了重复的子问题。

如果我们能够维护每个树根的两个场景的信息，让我们看看它是如何运行的。
重新定义rob(root)作为一个新的函数，该函数将返回两个元素的数组，其中第一个元素表示如果根没有被抢，可以被抢的最大金额，而第二个元素则表示如果被抢，则被抢的最大金额。

让我们把rob(root)与rob(root.left)和rob(root.right)联系起来。
在rob(root)的第1个元素中，我们只需要总结rob(root.left)和rob(root.right)的较大元素，因为root没有被抢，我们可以自由地抢夺它的左右子树。
然而，对于rob(root)的第2个元素，我们只需要将rob(root.left)和rob(root.right)的第1个元素相加，再加上从根本身中删除的值，因为在这种情况下，它保证了我们不能对根节点进行抢夺。
root.right。

正如您所看到的，通过跟踪两种场景的信息，我们将子问题解耦，而解决方案本质上归结为一个贪婪的问题。

 1 class Solution {
 2     public int rob(TreeNode root) {
 3         int[] res = new int[2];
 4         res = help(root);
 5         return Math.max(res[0],res[1]);
 6     }
 7     
 8     public int[] help(TreeNode root) {
 9         if(root==null) return new int[2];//终止条件
10         int[] left = help(root.left);
11         int[] right = help(root.right);
12         int[] res = new int[2];
13         res[0] = Math.max(left[0],left[1]) +Math.max(right[0],right[1]);
14         res[1] = root.val + left[0]+right[0];
15         return res;
16  
17     }
18 }