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 .思路：
一开始觉得只要分别计算不用层的和比较一下奇偶层哪个大就可以了，后来编译不过发现只有综合最大，可能不止隔一个层。所以后面使用动态规划，返回一个数组，res[0]代表不包含该节点的最大值，res[1]代表包含该节点的最大值。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int rob(TreeNode root) { if (root == null) { return 0; } int[] res = calucate(root); return res[0] > res[1] ? res[0] : res[1]; } private int[] calucate(TreeNode p) { int[] res = new int[2]; if (p == null) return res; int[] left = calucate(p.left); int[] right = calucate(p.right); // 不包含当前节点 res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // 包含当前节点 res[1] = left[0] + right[0] + p.val; return res; } }
