打家劫舍3

1. 题目描述

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

2. 思路

1. 思路一
   • 抢劫root+root.Left的左右子树+root.Right的左右子树
   • 抢劫root.Left+root.Right
   • 取两者中的较大者
2. 思路二
   1. DFS+记忆化

3. 实现

3.1. DFS

func rob(root *TreeNode) int {
	if root == nil {
		return 0
	}

	res := root.Val
	if root.Left != nil {
		res += rob(root.Left.Left)
		res += rob(root.Left.Right)
	}
	if root.Right != nil {
		res += rob(root.Right.Left)
		res += rob(root.Right.Right)
	}

	return Max(res, rob(root.Left)+rob(root.Right))
}

3.2. DFS+记忆化

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rob(root *TreeNode) int {
    memo := make(map[*TreeNode]int, 0)
    return dfs(root, memo)
}

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

    if val, ok := memo[root]; ok {
        return val
    }

    sum := root.Val
    if root.Left != nil {
        sum += dfs(root.Left.Left, memo)
        sum += dfs(root.Left.Right, memo)
    }
    if root.Right != nil {
        sum += dfs(root.Right.Left, memo)
        sum += dfs(root.Right.Right, memo)
    }

    memo[root] = max(sum, dfs(root.Left, memo) + dfs(root.Right, memo))
    return memo[root]
}

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

4. 参考

• 三种方法解决树形动态规划问题-从入门级代码到高效树形动态规划代码实现 - 打家劫舍 III - 力扣（LeetCode）