337. 打家劫舍 III.md

337. 打家劫舍 III

递归：

func rob(root *TreeNode) int {
     if root==nil{
         return 0
     }
     result :=0
     if root.Left !=nil{
          result+=rob(root.Left.Left)+rob(root.Left.Right)
     }
     if root.Right !=nil{
         result+=rob(root.Right.Left)+rob(root.Right.Right)
     }
     result+=root.Val

     return max(result,rob(root.Left)+rob(root.Right))
    
}

func max(a,b int)int{
    if a>=b{
        return a
    }
    return b
}

动态规划：

func rob(root *TreeNode) int {
    val := dfs(root)
    return max(val[0], val[1])
}

func dfs(node *TreeNode) []int {
    if node == nil {
        return []int{0, 0}
    }
    l, r := dfs(node.Left), dfs(node.Right)
    selected := node.Val + l[1] + r[1]
    notSelected := max(l[0], l[1]) + max(r[0], r[1])
    return []int{selected, notSelected}
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}