1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

// @Title: 打家劫舍 III (House Robber III)
// @Author: 15816537946@163.com
// @Date: 2019-11-25 09:57:18
// @Runtime: 4 ms
// @Memory: 5 MB
/*
 * @lc app=leetcode.cn id=337 lang=golang
 *
 * [337] 打家劫舍 III
 *
 * https://leetcode-cn.com/problems/house-robber-iii/description/
 *
 * algorithms
 * Medium (54.20%)
 * Likes:    168
 * Dislikes: 0
 * Total Accepted:    7.1K
 * Total Submissions: 13.2K
 * Testcase Example:  '[3,2,3,null,3,null,1]'
 *
 * 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。
 * 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
 * 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
 *
 * 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
 *
 * 示例 1:
 *
 * 输入: [3,2,3,null,3,null,1]
 *
 * ⁠    3
 * ⁠   / \
 * ⁠  2   3
 * ⁠   \   \
 * ⁠    3   1
 *
 * 输出: 7
 * 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
 *
 * 示例 2:
 *
 * 输入: [3,4,5,1,3,null,1]
 *
 * 3
 * ⁠   / \
 * ⁠  4   5
 * ⁠ / \   \
 * ⁠1   3   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 {
	res := helper(root)
	return max(res[0], res[1])
}

func helper(node *TreeNode) (res [2]int) {
	if node == nil {
		return
	}
	left := helper(node.Left)
	right := helper(node.Right)
	// 不包含根节点， 最大值为两个子树的最大值之和
	res[0] = max(left[0], left[1]) + max(right[0], right[1])
	// 包含根节点, 最大值为两个子树不包含根节点的最大值， 加上根节点的值
	res[1] = node.Val + left[0] + right[0]
	return
}

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

func rob(root *TreeNode) int {
	var dfs func(*TreeNode) (int, int)
	dfs = func(node *TreeNode) (int, int) {
		if node == nil {
			return 0, 0
		}
		la, lb := dfs(node.Left)
		ra, rb := dfs(node.Right)

		a := node.Val + lb + rb
		b := max(la, lb) + max(ra, rb)

		return a, b
	}
	a, b := dfs(root)
	return max(a, b)
}

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