337. 打家劫舍III

题目描述：

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1：

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

示例 2：

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

提示：

• 树的节点数在 [1, 10^4] 范围内
• 0 <= Node.val <= 10^4

---

解题分析及思路：

此问题与198、打家劫舍 及 213、打家劫舍II 的进阶，与之不同的是，这里的房屋排列成了二叉树的结构。

对于二叉树的遍历，可以查看二叉树的介绍，里面还有三种不同类型的遍历方式。

此题一样，可以分为两种情况：

• 如果偷取了根节点，则不能偷取其左右子节点，但可以偷取其左右子节点的子节点，即当前节点的值 + 不偷取左子树的最大值 + 不偷取右子树的最大值。
• 如果不偷取根节点，则可以偷取其左右子节点，即 max(偷取左子树的最大值, 不偷取左子树的最大值) + max(偷取右子树的最大值, 不偷取右子树的最大值)

那么对应动态规划解法：

1. 定义状态：我们定义一个递归函数 Func(node *TreeNode) (int, int)，其中 Func 函数返回一个二元组，表示小偷在当前节点盗取和不盗取的最大金额。

2. 找到状态转移方程 ：对于当前节点 node，其左子树返回的二元组为 (l1, l2)，表示在左子树中盗取和不盗取的最大金额。 右子树返回的二元组为 (r1, r2)。

   • 则当前节点的盗取最大金额为 node.Val + l2 + r2
   • 不盗取最大金额为 max(l1, l2) + max(r1, r2)。

3. 初始化：递归终止条件为节点为空，此时返回 (0, 0)。

4. 递推求解：通过递归调用 Func 函数，逐步求解每个节点的盗取和不盗取的最大金额。

5. 计算最终结果 ：最终结果为返回的二元组的最大值。

func rob(root *TreeNode) int {
	max := func(a, b int) int {
		if b > a {
			return b
		}
		return a
	}
	var Func func(node *TreeNode) (int, int)
	Func = func(node *TreeNode) (int, int) {
		if node == nil {
			return 0, 0
		}
		// l1: 偷取左子树的最大值 l2: 不偷取左子树的最大值
		l1, l2 := Func(node.Left)
		// r1: 偷取右子树的最大值 r2: 不偷取右子树的最大值
		r1, r2 := Func(node.Right)
		// 偷取当前节点的最大值 = 当前节点的值 + 不偷取左子树的最大值 + 不偷取右子树的最大值
		// 不偷取当前节点的最大值 = max(偷取左子树的最大值, 不偷取左子树的最大值) + max(偷取右子树的最大值, 不偷取右子树的最大值)
		return node.Val + l2 + r2, max(l1, l2) + max(r1, r2)
	}
	return max(Func(root))
}

复杂度：

• 时间复杂度：O(n)，其中 n 为二叉树的节点个数。每个节点只需访问一次。
• 空间复杂度：O(h)，其中 h 为二叉树的高度。递归调用栈的深度为树的高度。

执行结果：

• 执行耗时:3 ms,击败了88.42% 的Go用户
• 内存消耗:4.9 MB,击败了73.17% 的Go用户