[Day18]-[动态规划] 打家劫舍 3

输入: root = [3,2,3,null,3,null,1]输出: 7 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

输入: root = [3,4,5,1,3,null,1]输出: 9解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func rob(root *TreeNode) int {	var max func(x, y int) int       // 取最大值	var dfs func(*TreeNode)          // 递归函数	var rob func(root *TreeNode) int // 最大收益	var f = make(map[*TreeNode]int)  // 选择o节点的最大值	var g = make(map[*TreeNode]int)  // 不选择o节点的最大值
	max = func(x, y int) int {		if x > y {			return x		}
		return y	}
	// 后序遍历	dfs = func(node *TreeNode) {		// base case		if node == nil {			return		}
		dfs(node.Left)		dfs(node.Right)		// 做选择		// 选择o节点，那么就不能选择子节点 f选择，g不选择		f[node] = node.Val + g[node.Left] + g[node.Right]		// 不选择o节点，那么子节点可选择或不选择，最两种选择的最大值		g[node] = max(f[node.Left], g[node.Left]) + max(f[node.Right], g[node.Right])	}
	rob = func(root *TreeNode) int {		dfs(root)		return max(f[root], g[root])	}
    return rob(root)}