p337

发表于 | 分类于 |

LeetCode p337 House Robber III 题解

1.题目：

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.

题意：

一个小偷去一个呈树状分布的小区行窃。如果同时偷了父节点和他的子节点，
就会被警察发现。求在不被警察发现的情况下能够偷多少钱。

2.解题思路:

DP。从根向上，每次记得把节点的值更新为到此为止的最优值。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
/**
 * 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) {
        int count = 0;
		if (root == null)
			return 0;
		int left = rob(root.left);
		int right = rob(root.right);
		int kid = left + right;
		if (root.left != null) {
			count += root.left.left == null ? 0 : root.left.left.val;
			count += root.left.right == null ? 0 : root.left.right.val;
		}

		if (root.right != null) {
			count += root.right.left == null ? 0 : root.right.left.val;
			count += root.right.right == null ? 0 : root.right.right.val;
		}
		// System.out.println(left+"  "+right);
		root.val = Math.max(kid, count + root.val);// 注意
		return root.val;
    }
}

4.一些总结：