难度中等 1479

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 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

提示：

# 前言

BFS： dp[i] 表示前 i 层的最高金额。不行

# 记忆化搜索

	class Solution {

	public int rob(TreeNode root) {
	return dfs(root);
	}
	Map<TreeNode, Integer> used = new HashMap<>();
	public int dfs(TreeNode root) {
	if (root == null) {
	return 0;
	}
	if (used.containsKey(root)) {
	return used.get(root);
	}
	// 偷取该节点
	// - 下一层就不偷，去下下层偷或者不偷的最大金额 + 当前节点
	int money = root.val;
	if (root.left != null) {
	money += dfs(root.left.left) + dfs(root.left.right);
	}
	if (root.right != null) {
	money += dfs(root.right.left) + dfs(root.right.right);
	}
	// 不偷取该节点
	// - 下一层偷或者不偷的最大金额 + 当前节点
	int notStole = dfs(root.left) + dfs(root.right);

	used.put(root,Math.max(money, notStole));
	return used.get(root);
	}

	}

$dfs(u, 0)$ ：以 u 为根节点不偷的最大金额

$dfs(u, 1)$ ：以 u 为根节点偷的最大金额

当前点要么偷，要么不偷

当前根节点的最大金额： $ans = max(stole, noStole)$

若当前节点不偷，为什么是其左右孩子可以偷与不偷，而不是偷

如上图所示

	class Solution {

	public int rob(TreeNode root) {
	int[] res = dfs(root);
	return Math.max(res[0], res[1]);
	}

	public int[] dfs(TreeNode root) {
	//stole 表示偷该节点的最大金额
	// stole = 左孩子不偷的最大金额 + 右孩子不偷的最大金额 + 当前节点偷的金额
	// stole = left[0] + right[0] + root.val
	//noStole 表示不偷该节点的最大金额 = 孩子节点偷与不偷的最大金额
	// noStole = max (左孩子偷的最大金额，左孩子不偷的最大金额) + max (= 右孩子偷的最大金额，右孩子不偷的最大金额)
	// noStole = Math.max(left[1], left[0]) + Math.max(right[1], right[0])
	if (root == null) {
	return new int[2];
	}
	int[] left = robTree(root.left);
	int[] right = robTree(root.right);
	// 不偷当前节点
	// - 左右孩子偷 / 不偷的最大金额 + 当前节点
	int noStole = Math.max(left[1], left[0]) + Math.max(right[1], right[0]);
	// 偷当前节点
	// - 左右孩子不偷的最大金额 + 当前节点
	int stole = left[0] + right[0] + root.val;
	return new int[]{noStole, stole};
	}

	}