KK's blog

每天积累多一些

0%

LeetCode 337 House Robber III

Posted on Edited on Disqus:

LeetCode



The thief has found himself a new place for his thievery again. There is only one entrance to this area, called 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 form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1:



Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.


Example 2:



Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.


Constraints:

The number of nodes in the tree is in the range [1, 10<sup>4</sup>]. 0 <= Node.val <= 10<sup>4</sup>

题目大意：

二叉树，相隔一层投，求最大值

解题思路：

多状态DP。返回值为，第一个是以root为结尾的最大值，第二个为儿子层总和的最大值。

与LeetCode 309 Best Time to Buy and Sell Stock with Cooldown相似

DFS解题步骤：

N/A

注意事项：

  1. 以儿子层的前n最大值 = max(left) + max(right)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def rob2(self, root: TreeNode) -> int:
	res = self.dfs2(root)
	return max(res)

def dfs2(self, root):
	if not root:
		return (0, 0)

	left = self.dfs2(root.left)
	right = self.dfs2(root.right)

	return root.val + left[1] + right[1], max(left) + max(right)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

记忆法搜索算法II解题思路：

递归式：

1
2
f(n) = root.val + g(root.left) + g(root.right)  
g(n) = max(f(root.left), g(root.left)) + max(f(root.right), g(root.right))

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def rob(self, root: TreeNode) -> int:
	f, g = {}, {}
	res = self.dfs(root, f, g)
	return max(res)

def dfs(self, root, f, g):
	if not root:
		return (0, 0)
	if root.left not in f or root.left not in g:
		f[root.left], g[root.left] = self.dfs(root.left, f, g)
	if root.right not in f or root.right not in g:
		f[root.right], g[root.right] = self.dfs(root.right, f, g)
	f[root] = root.val + g[root.left] + g[root.right]
	g[root] = max(f[root.left], g[root.left]) + max(f[root.right], g[root.right])
	return f[root], g[root]

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

Free mock interview