Skip to content

Latest commit

 

History

History
99 lines (69 loc) · 3.41 KB

0337-house-robber-iii.adoc

File metadata and controls

99 lines (69 loc) · 3.41 KB
Raw

337. House Robber III

{leetcode}/problems/house-robber-iii/[LeetCode - 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:
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: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

解题分析

由于题目给出示例的误导，这里存在一个误区：在不选父节点时，子树选最优解不受任何干扰，也就是说子树的跟节点可选也可以不选。所以，可以将这个问题简化为，分选根节点和不选根节点，两种情况考虑：

  1. 选父节点，则子树必定不能选根节点；

  2. 如果不选跟节点，则子树可以在选根节点和不选跟节点中选最优解就好。

然后在这上面两种情况中选出最优解。

思考题

尝试使用动态规划来解决这个问题。

参考资料

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 = <font color="red" style="font-family: sans-serif, Arial, Verdana, "Trebuchet MS";">3 + <font color="red" style="font-family: sans-serif, Arial, Verdana, "Trebuchet MS";">3  + <font color="red" style="font-family: sans-serif, Arial, Verdana, "Trebuchet MS";">1  = <b style="font-family: sans-serif, Arial, Verdana, "Trebuchet MS";">7* .

Example 2:

Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \
 1   3   1

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + <font color="red">5 = 9.
link:{sourcedir}/_0337_HouseRobberIII.java[role=include]