leetcode 337. 打家劫舍 III

题解

两种情况,根的值加上不直接相连的左右子树的值,或者不要根植,直接是根的左右子树值的和,比较两种情况下的大小,同时可以加上哈希表返回已经计算过的值

示例代码(go)

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
30
31
32
33
34
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rob(root *TreeNode) int {
stateMap := make(map[*TreeNode]int)
return dfs(root, stateMap)
}

func dfs(root *TreeNode, stateMap map[*TreeNode]int) int {
if root == nil {
return 0
}
if _, ok := stateMap[root]; ok {
return stateMap[root]
}
res := root.Val
if root.Left != nil {
res += dfs(root.Left.Left, stateMap) + dfs(root.Left.Right, stateMap)
}
if root.Right != nil {
res += dfs(root.Right.Left, stateMap) + dfs(root.Right.Right, stateMap)
}
val := dfs(root.Left, stateMap) + dfs(root.Right, stateMap)
if res < val {
res = val
}
stateMap[root] = res
return stateMap[root]
}