在树上动态规划

func rob(root *TreeNode) int {
	var dfs func(node *TreeNode, selected bool) int
	dfs = func(node *TreeNode, selected bool) int {
		if node == nil {
			return 0
		}
		leftNotTake := dfs(node.Left, false)
		rightNotTake := dfs(node.Right, false)
		if selected {
			return node.Val + leftNotTake + rightNotTake
		}
		leftTake := dfs(node.Left, true)
		rightTake := dfs(node.Right, true)
		return max(leftTake, leftNotTake) + max(rightTake, rightNotTake)
	}
	return max(dfs(root, true), dfs(root, false))
}

func rob(root *TreeNode) int {
	return max(dfs(root))
}

func dfs(node *TreeNode) (int, int) {
	if node == nil {
		return 0, 0
	}
	leftTake, leftNotTake := dfs(node.Left)
	rightTake, rightNotTake := dfs(node.Right)
	take := node.Val + leftNotTake + rightNotTake
	notTake := max(leftTake, leftNotTake) + max(rightTake, rightNotTake)
	return take, notTake
}

func minCameraCover0(root *TreeNode) int {
	var help func(*TreeNode, bool, bool) int
	// placeCam，是否在 node 处安装相机；
	// watched，node 是否被父节点或自身监控(递归过程是自上而下，对于当前节点，只知道父节点或自身是否监控自己，并不知道子节点的情况)
	help = func(node *TreeNode, placeCam, watched bool) int {
		if node == nil {
			if placeCam {
				return math.MaxInt32
			}
			return 0
		}

		leftPlaceWatch := help(node.Left, true, true)
		rightPlaceWatch := help(node.Right, true, true)

		if placeCam {
			leftNotPlaceWatch := help(node.Left, false, true)
			rightNotPlaceWatch := help(node.Right, false, true)
			return 1 + min(
				leftNotPlaceWatch+rightNotPlaceWatch, // 两个子节点都不安装相机
				leftPlaceWatch+rightNotPlaceWatch,    // 仅左子节点安装相机
				leftNotPlaceWatch+rightPlaceWatch) // 仅右子节点安装相机
			// 两个子节点都装相机的情况不用考虑
		}
		leftNotPlaceNotWatch := help(node.Left, false, false)
		rightNotPlaceNotWatch := help(node.Right, false, false)
		res := min(
			leftPlaceWatch+rightPlaceWatch,       // 两个子节点都安装相机
			leftPlaceWatch+rightNotPlaceNotWatch, // 左装右不装
			leftNotPlaceNotWatch+rightPlaceWatch) // 右装左不装
		if watched {
			res = min(res, leftNotPlaceNotWatch+rightNotPlaceNotWatch) // 左右都不装，当前节点是被其父节点监控的
		}
		return res

	}
	return min(help(root, true, true), help(root, false, false))
}

func minCameraCover(root *TreeNode) int {
	var dfs func(node *TreeNode) (int, int, int)
	dfs = func(root *TreeNode) (int, int, int) {
		if root == nil {
			return math.MaxInt32, 0, 0
		}
		lHasCam, lNoCamWatchedByParent, lNoCamWatchedBySons := dfs(root.Left)
		rHasCam, rNoCamWatchedByParent, rNoCamWatchedBySons := dfs(root.Right)

		hasCam := 1 + min(lHasCam, lNoCamWatchedByParent, lNoCamWatchedBySons) +
			min(rHasCam, rNoCamWatchedByParent, rNoCamWatchedBySons)

		noCamWatchedByParent := min(lHasCam, lNoCamWatchedBySons) +
			min(rHasCam, rNoCamWatchedBySons)

		noCamWatchedBySons := min(lHasCam+rNoCamWatchedBySons, lHasCam+rHasCam, lNoCamWatchedBySons+rHasCam)

		return hasCam, noCamWatchedByParent, noCamWatchedBySons
	}
	hasCam, _, noCamWatchedBySons := dfs(root)
	return min(hasCam, noCamWatchedBySons)
}

func min(s ...int) int {
	res := s[0]
	for _, v := range s[1:] {
		if res > v {
			res = v
		}
	}
	return res
}

type state = int

const (
	hasCamera state = iota
	covered
	notCovered
)

func minCameraCover(root *TreeNode) int {
	res := 0
	var dfs func(*TreeNode) state
	dfs = func(root *TreeNode) state {
		if root == nil {
			return covered // 贪心，为了使的叶子结点尽量不放置相机
		}
		left, right := dfs(root.Left), dfs(root.Right)
		if left == notCovered || right == notCovered {
			res++
			return hasCamera
		}
		if left == covered && right == covered {
			return notCovered
		}
		return covered
	}

	if dfs(root) == notCovered {
		res++
	}
	return res
}