Leetcode-Question-337: House Robber III

原文链接:
https://leetcode.com/problems/house-robber-iii/

题目描述:
337. House Robber III
Difficulty: Medium

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.

解析:
参考https://leetcode.com/discuss/91652/c-java-python-%26-explanation

Let f1(node) be the value of maximum money we can rob from the subtree with node as root ( we can rob node if necessary).
f2(node) be the value of maximum money we can rob from the subtree with node as root but without robbing node.
Then we have
f2(node) = f1(node.left) + f1(node.right) and
f1(node) = max( f2(node.left)+f2(node.right)+node.value, f2(node) ).

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注