一、题目描述
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。
这个地区只有一个入口，我们称之为根。
除了“根”之外，每栋房子有且只有一个“父“房子与之相连。
一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 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.
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 打家劫舍III（ LeetCode 337 ）：https://leetcode-cn.com/problems/house-robber-iii/submissions/
class Solution {
public int rob(TreeNode root) {
// 每个节点都有两种选择：偷、不偷
// 从叶子节点开始判断，直到来到根节点
int[] res = chooseNode(root);
// 选择当前节点偷和不偷抉择时的较大值
return Math.max(res[0], res[1]);
}
private int[] chooseNode(TreeNode node) {
// 递归终止条件
// 即在叶子节点的时候，叶子节点的左右子节点为 null
// 继续调用下去就会返回给叶子节点，它的左右子树的选择的金额都是 0
if (node == null) {
return new int[]{0, 0};
}
// 否则的话，说明当前节点有值
// 需要判断，当前节点是偷还是不偷
// 1、如果选择偷，那么左子节点不能偷，这个时候需要获取不偷左子节点时的最大金额
// 2、如果选择偷，那么右子节点不能偷，这个时候需要获取不偷右子节点时的最大金额
// 3、如果选择不偷，那么可以偷左右子节点，这个时候的最大金额为左右子节点最大金额之和
// dp[0] 表示的是以当前 node 为根节点的子树能够偷取的最大金额，并且此时采取【不偷】 node 这个节点的策略
// dp[1] 表示的是以当前 node 为根节点的子树能够偷取的最大金额，并且此时采取【偷】 node 这个节点的策略
int[] dp = new int[2];
// 先去计算左子节点的选择
int[] left = chooseNode(node.left);
// 再去计算右子节点的选择
int[] right = chooseNode(node.right);
// 如果选择不偷，那么可以偷左右子节点，这个时候的最大金额为左右子节点最大金额之和
dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
// 1、如果选择偷，那么左子节点不能偷，这个时候需要获取不偷左子节点时的最大金额
// 2、如果选择偷，那么右子节点不能偷，这个时候需要获取不偷右子节点时的最大金额
// 3、再加上当前节点的金额
dp[1] = left[0] + right[0] + node.val;
return dp;
}
}
2、C++ 代码
class Solution {
public:
int rob(TreeNode* root) {
// 每个节点都有两种选择：偷、不偷
// 从叶子节点开始判断，直到来到根节点
vector<int> res = chooseNode(root);
// 选择当前节点偷和不偷抉择时的较大值
return max(res[0], res[1]);
}
private:
vector<int> chooseNode(TreeNode* node) {
// 递归终止条件
// 即在叶子节点的时候，叶子节点的左右子节点为 null
// 继续调用下去就会返回给叶子节点，它的左右子树的选择的金额都是 0
if (node == NULL) {
return vector<int>{0, 0};
}
// 否则的话，说明当前节点有值
// 需要判断，当前节点是偷还是不偷
// 1、如果选择偷，那么左子节点不能偷，这个时候需要获取不偷左子节点时的最大金额
// 2、如果选择偷，那么右子节点不能偷，这个时候需要获取不偷右子节点时的最大金额
// 3、如果选择不偷，那么可以偷左右子节点，这个时候的最大金额为左右子节点最大金额之和
// dp[0] 表示的是以当前 node 为根节点的子树能够偷取的最大金额，并且此时采取【不偷】 node 这个节点的策略
// dp[1] 表示的是以当前 node 为根节点的子树能够偷取的最大金额，并且此时采取【偷】 node 这个节点的策略
vector<int> dp(2);
// 先去计算左子节点的选择
vector<int> left = chooseNode(node->left);
// 再去计算右子节点的选择
vector<int> right = chooseNode(node->right);
// 如果选择不偷，那么可以偷左右子节点，这个时候的最大金额为左右子节点最大金额之和
dp[0] = max(left[0], left[1]) + max(right[0], right[1]);
// 1、如果选择偷，那么左子节点不能偷，这个时候需要获取不偷左子节点时的最大金额
// 2、如果选择偷，那么右子节点不能偷，这个时候需要获取不偷右子节点时的最大金额
// 3、再加上当前节点的金额
dp[1] = left[0] + right[0] + node->val;
return dp;
}
};
3、Python 代码
class Solution:
def rob(self, root: TreeNode) -> int:
# 每个节点都有两种选择：偷、不偷
# 从叶子节点开始判断，直到来到根节点
res = self.chooseNode(root)
# 选择当前节点偷和不偷抉择时的较大值
return max(res[0], res[1])
def chooseNode(self, node):
# 递归终止条件
# 即在叶子节点的时候，叶子节点的左右子节点为 null
# 继续调用下去就会返回给叶子节点，它的左右子树的选择的金额都是 0
if node is None:
return (0, 0)
# 否则的话，说明当前节点有值
# 需要判断，当前节点是偷还是不偷
# 1、如果选择偷，那么左子节点不能偷，这个时候需要获取不偷左子节点时的最大金额
# 2、如果选择偷，那么右子节点不能偷，这个时候需要获取不偷右子节点时的最大金额
# 3、如果选择不偷，那么可以偷左右子节点，这个时候的最大金额为左右子节点最大金额之和
# dp[0] 表示的是以当前 node 为根节点的子树能够偷取的最大金额，并且此时采取【不偷】 node 这个节点的策略
# dp[1] 表示的是以当前 node 为根节点的子树能够偷取的最大金额，并且此时采取【偷】 node 这个节点的策略
dp = [ 0 ,0 ]
# 先去计算左子节点的选择
left = self.chooseNode(node.left)
# 再去计算右子节点的选择
right = self.chooseNode(node.right)
# 如果选择不偷，那么可以偷左右子节点，这个时候的最大金额为左右子节点最大金额之和
dp[0] = max(left[0], left[1]) + max(right[0], right[1])
# 1、如果选择偷，那么左子节点不能偷，这个时候需要获取不偷左子节点时的最大金额
# 2、如果选择偷，那么右子节点不能偷，这个时候需要获取不偷右子节点时的最大金额
# 3、再加上当前节点的金额
dp[1] = left[0] + right[0] + node.val
return dp
