337.打家劫舍 III

后序遍历+动态规划

看到树形结构优先考虑root和左右子树的关系。

使用后序遍历是因为需要得到两个子节点的状态才能计算当前节点。

时间复杂度：O(N)
空间复杂度：O(N)

func rob(root *TreeNode) int {
    // root[1] = root.left[0] + root.right[0] 
    // root[0] = max(root.left[0], root.left[1]) + max(root.right[0], root.right[1])

    var dfs func(*TreeNode) []int
    dfs = func(root *TreeNode) []int {
        if root == nil {
            return []int{0, 0}
        }

		// 得到子节点的状态
        left := dfs(root.Left)
        right := dfs(root.Right)

		// 状态转移
        selected := root.Val + left[0] + right[0]
        noSelected := max(left[0], left[1]) + max(right[0], right[1])

		// 返回状态给上一层使用
        return []int{noSelected, selected}
    }

    temp := dfs(root)

    return max(temp[0], temp[1])
}

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