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%