共计 1457 个字符，预计需要花费 4 分钟才能阅读完成。
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:Input: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
Output: 7 Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:Input: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
Output: 9Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
难度：medium
题目：小偷又发现了一个新的地方来实施的偷盗计划。这个地方只有一个入口叫“根”。除了这个根之外，每个房间有且仅有一个父房间。一番游览过后，聪明的小偷意识到这里所有的房子形成了一棵二叉树。如果在同一晚上有任何两个相邻的房子遭遇偷盗就会触发警报。
在这个晚上小偷如何决策在不触发警报的情况下获取最大的盗资。
思路：二叉树遍历
Runtime: 733 ms, faster than 27.11% of Java online submissions for House Robber III.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) {val = x;}
* }
*/
class Solution {
// rob root, g(root) = root.val + f(root.left.left) + f(root.left.right) + f(root.right.left) + f(root.right.right)
// not rob root, g(not_root) = f(root.left) + f(root.right);
// f(root) = Math.max(g(root), g(not_root))
public int rob(TreeNode root) {
if (null == root) {
return 0;
}
TreeNode left = root.left;
int leftSum = (null == left) ? 0 : (rob(left.left) + rob(left.right));
TreeNode right = root.right;
int rightSum = (null == right) ? 0 : (rob(right.left) + rob(right.right));
return Math.max(root.val + leftSum + rightSum, rob(left) + rob(right));
}
}
