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
28
29
| func rob(root *TreeNode) int {
result := robSub(root)
return max(result[0], result[1])
}
func robSub(root *TreeNode) [2]int {
if root == nil {
return [2]int{0, 0}
}
leftResult := robSub(root.Left)
rightResult := robSub(root.Right)
// result[0] 表示不抢劫当前节点的最大金额
// result[1] 表示抢劫当前节点的最大金额
result := [2]int{}
result[0] = max(leftResult[0], leftResult[1]) + max(rightResult[0], rightResult[1])
result[1] = root.Val + leftResult[0] + rightResult[0]
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
|