337. House Robber III

337. 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.

题目大意

小偷又找到了新的目标,这条街上的房子呈二叉树排列,同一晚上相邻的两层被偷会引发警报。

解题思路

递归,深度优先搜索(DFS
当遍历到某一层时,偷当前层和不偷的最大值。

代码

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func rob(_ root: TreeNode?) -> Int {
func dfs(tree: TreeNode?) -> (Int, Int) {
guard let t = tree else { return (0, 0) }
let left = dfs(tree: t.left)
let right = dfs(tree: t.right)
let noRob = max(left.0, left.1) + max(right.0, right.1)
let rob = t.val + left.0 + right.0
return (noRob, rob)
}
let ans = dfs(tree: root)
return max(ans.0, ans.1)
}
}
0%