大家好，我是吴师兄。
今天继续分享 LeetCode 上比较有意思的问题或者回答，闲暇之余，博君一笑。
先看评论：
这个小偷这么聪明为啥还要偷东西。
这个评论来源于 LeetCode 337 号问题：打家劫舍III。
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。
这个地区只有一个入口，我们称之为根。
除了“根”之外，每栋房子有且只有一个“父“房子与之相连。
一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
举个例子：
确实，这个小偷挺聪明的，知道二叉树、知道动态规划。。。
聪明的小偷是如何思考的呢？
当他站在小区入口，即根的位置时，他会纠结：这个房间，偷还是不偷？
因为他两眼一抹黑，眼中只看到到 3 这个房间，后续其它房间的信息不清楚，偷的话，后面两个子树更值钱，那亏了；不偷的话，后面两个子树都不值钱，也亏了。
所以，与其这么纠结，就先从叶子节点开始吧，不从大门进去，直接翻墙进去。
这里给大家留一个思考题，为什么从叶子节点思考比从根节点思考方便很多。
这个时候，小偷面对的就是一排房间，口袋空空，我全都要。
为了描述方便，这里用房间号指代房间的价值。
最底层的所有房间都偷个精光后，接下来，沿着小路来到上面的房间。
面对 4 号房间时，小偷摸了摸口袋，我偷了 1 和 3 号房间，攒了 4 块钱，但不能偷 4 号房间了；假设我把 1 和 3 号的房间的钱都丢了，那我就能偷 4 号房间了。
聪明的小偷选择偷 4 号房间。
同样的，面对 5 号房间时，小偷摸了摸口袋，我偷了 1 号房间，攒了 1 块钱，但不能偷 5 号房间了；假设我把 1 号的房间的钱都丢了，那我就能偷 5 号房间了。
聪明的小偷选择偷 5 号房间。
最后，当小偷来到根节点时，他又可以抉择：
- 1、不偷 3 号房间，可以偷 4 号和 5 号房间，价值为 9 。
- 2、偷 3 号房间，不偷 4 号和 5 号房间，本身价值为 3，由于不偷 4 时，可以偷它的子树房间，前面计算金额为 4；由于不偷 5 时，可以偷它的子树房间，前面计算金额为 1；累加起来就是 8。
于是，最终小偷的方案是偷 4 号和 5 号房间。
最后，给出代码：
代码语言：javascript复制// 登录 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;
}
}
提交，击败 100% 。
看来，我做小偷也挺有前途的。。。
