337. 打家劫舍 III
题目描述
某片住宅区的房子连成一棵二叉树，入口是根节点 root。每个节点代表一间房子，节点值是屋里的现金数。树用层序数组表示，例如 [3,2,3,null,3,null,1]，null 表示空位置。
小偷要在一晚内偷若干间房子。如果两间直接相连的房子（即父子节点）在同一晚都被偷，就会触发警报。
返回在不触发警报的前提下，小偷能偷到的最大金额。
示例 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。
数据范围
- 节点数在
[1, 10^4]范围内 0 <= Node.val <= 10^4
解题思路：树形 DP（偷/不偷二元组）
树形 DP。对每个节点后序计算一对数：rob 表示偷这个节点时子树的最大收益，skip 表示不偷它时的最大收益。偷它，两个孩子都不能偷：rob = val + l_skip + r_skip；不偷它，每个孩子可偷可不偷：skip = max(l_rob, l_skip) + max(r_rob, r_skip)。答案是根节点两个值中较大的。
为什么正确
dfs(node) 返回的 (rob, skip) 分别是以 node 为根的子树在“偷 node”和“不偷 node”两种前提下的最大收益。
复杂度分析
时间 O(n)，空间 O(h)，h 为树高。
易错点
“偷祖父和孙子”或“隔层偷”这类贪心做法是错的，例如 [4,1,null,2,null,3] 的最优解是偷 4 和 3（相隔两层）。不偷当前节点时，孩子也不一定要偷，要取 max。另外不要写成不带记忆的“偷孙子”递归，会退化为指数时间。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return 0, 0
l_rob, l_skip = dfs(node.left)
r_rob, r_skip = dfs(node.right)
rob = node.val + l_skip + r_skip
skip = max(l_rob, l_skip) + max(r_rob, r_skip)
return rob, skip
return max(dfs(root))class Solution {
int[] dfs(TreeNode node) {
if (node == null) {
return new int[]{0, 0};
}
int[] l = dfs(node.left);
int[] r = dfs(node.right);
int rob = node.val + l[1] + r[1];
int skip = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
return new int[]{rob, skip};
}
public int rob(TreeNode root) {
int[] res = dfs(root);
return Math.max(res[0], res[1]);
}
}class Solution {
public:
pair<int, int> dfs(TreeNode* node) {
if (!node) {
return {0, 0};
}
auto [l_rob, l_skip] = dfs(node->left);
auto [r_rob, r_skip] = dfs(node->right);
int rob = node->val + l_skip + r_skip;
int skip = max(l_rob, l_skip) + max(r_rob, r_skip);
return {rob, skip};
}
int rob(TreeNode* root) {
auto [a, b] = dfs(root);
return max(a, b);
}
};func rob(root *TreeNode) int {
var dfs func(node *TreeNode) (int, int)
dfs = func(node *TreeNode) (int, int) {
if node == nil {
return 0, 0
}
lRob, lSkip := dfs(node.Left)
rRob, rSkip := dfs(node.Right)
robV := node.Val + lSkip + rSkip
skip := max(lRob, lSkip) + max(rRob, rSkip)
return robV, skip
}
a, b := dfs(root)
return max(a, b)
}var rob = function(root) {
const dfs = (node) => {
if (!node) {
return [0, 0];
}
const [lRob, lSkip] = dfs(node.left);
const [rRob, rSkip] = dfs(node.right);
const robV = node.val + lSkip + rSkip;
const skip = Math.max(lRob, lSkip) + Math.max(rRob, rSkip);
return [robV, skip];
};
return Math.max(...dfs(root));
};function rob(root: TreeNode | null): number {
const dfs = (node: TreeNode | null): [number, number] => {
if (!node) {
return [0, 0];
}
const [lRob, lSkip] = dfs(node.left);
const [rRob, rSkip] = dfs(node.right);
const robV = node.val + lSkip + rSkip;
const skip = Math.max(lRob, lSkip) + Math.max(rRob, rSkip);
return [robV, skip];
};
return Math.max(...dfs(root));
}其他解法
记忆化搜索每个节点只存一个最优值，靠哈希表去重；主解法每个节点返回偷和不偷两个值，一次后序遍历完成，不需要哈希表。
解法 2：记忆化搜索（祖孙转移） 时间 O(n)，空间 O(n)
f(node) 表示以 node 为根的子树能偷到的最大金额。偷 node 时不能偷孩子，金额是 node.val 加上四个孙子的 f；不偷 node 时金额是两个孩子的 f 之和。两者取大。用哈希表记住每个节点的 f，避免孙子被重复计算。
状态定义和「打家劫舍」线性版本一致，容易想到。需要哈希表保存所有节点的结果，常数和空间都比二元组写法大。不加记忆化会退化为指数级。
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
memo = {}
def f(node):
if not node:
return 0
if node in memo:
return memo[node]
take = node.val
if node.left:
take += f(node.left.left) + f(node.left.right)
if node.right:
take += f(node.right.left) + f(node.right.right)
skip = f(node.left) + f(node.right)
memo[node] = max(take, skip)
return memo[node]
return f(root)class Solution {
Map<TreeNode, Integer> memo = new HashMap<>();
int f(TreeNode node) {
if (node == null) return 0;
Integer cached = memo.get(node);
if (cached != null) return cached;
int take = node.val;
if (node.left != null) take += f(node.left.left) + f(node.left.right);
if (node.right != null) take += f(node.right.left) + f(node.right.right);
int skip = f(node.left) + f(node.right);
int best = Math.max(take, skip);
memo.put(node, best);
return best;
}
public int rob(TreeNode root) {
return f(root);
}
}class Solution {
public:
unordered_map<TreeNode*, int> memo;
int f(TreeNode* node) {
if (!node) return 0;
auto it = memo.find(node);
if (it != memo.end()) return it->second;
int take = node->val;
if (node->left) take += f(node->left->left) + f(node->left->right);
if (node->right) take += f(node->right->left) + f(node->right->right);
int skip = f(node->left) + f(node->right);
return memo[node] = max(take, skip);
}
int rob(TreeNode* root) {
return f(root);
}
};func rob(root *TreeNode) int {
memo := map[*TreeNode]int{}
var f func(node *TreeNode) int
f = func(node *TreeNode) int {
if node == nil {
return 0
}
if v, ok := memo[node]; ok {
return v
}
take := node.Val
if node.Left != nil {
take += f(node.Left.Left) + f(node.Left.Right)
}
if node.Right != nil {
take += f(node.Right.Left) + f(node.Right.Right)
}
skip := f(node.Left) + f(node.Right)
memo[node] = max(take, skip)
return memo[node]
}
return f(root)
}var rob = function(root) {
const memo = new Map();
const f = (node) => {
if (!node) return 0;
if (memo.has(node)) return memo.get(node);
let take = node.val;
if (node.left) take += f(node.left.left) + f(node.left.right);
if (node.right) take += f(node.right.left) + f(node.right.right);
const skip = f(node.left) + f(node.right);
const best = Math.max(take, skip);
memo.set(node, best);
return best;
};
return f(root);
};function rob(root: TreeNode | null): number {
const memo = new Map<TreeNode, number>();
const f = (node: TreeNode | null): number => {
if (!node) return 0;
if (memo.has(node)) return memo.get(node)!;
let take = node.val;
if (node.left) take += f(node.left.left) + f(node.left.right);
if (node.right) take += f(node.right.left) + f(node.right.right);
const skip = f(node.left) + f(node.right);
const best = Math.max(take, skip);
memo.set(node, best);
return best;
};
return f(root);
}