【LeetCode】动态规划—337. 打家劫舍 III（附完整Python/C++代码）

小开 ALSKai

发布于 2026-06-16 19:37:55

1460

动态规划—337. 打家劫舍 III

题目描述
前言
基本思路
- 1. 问题定义
- - 二叉树的限制：
- 2. 理解问题和递推关系
- - 核心思路：
  - 状态定义：
  - 状态转移方程：
  - 递归求解：
- 3. 解决方法
- - 递归 + 动态规划方法
  - 伪代码：
- 4. 进一步优化
- 5. 小总结
Python代码
- - Python代码解释
C++代码
- - C++代码解释
总结

题目描述

前言

打家劫舍 III 是 打家劫舍 系列问题中的一个变种。这里的房屋排列不再是线性排列，而是形成了一棵二叉树，每个节点代表一个房子，每个房子内有一定的钱。相邻的房子（即父子关系）不能同时被抢。我们的目标是找出在这棵二叉树中，能够抢劫到的最大金额。

基本思路

1. 问题定义

给定一个二叉树结构，每个节点表示一个房子，房子里有一定的钱，要求我们在不抢劫相邻房子的情况下，抢劫到的最大金额。

二叉树的限制：

每个房子与其子房子相邻，如果父节点被抢劫，那么子节点不能被抢。
可以选择抢劫或不抢劫某个房子。

2. 理解问题和递推关系

核心思路：

对于每个节点，我们有两种选择：

抢劫当前节点：如果抢劫当前节点，那么它的左右子节点不能被抢劫。
不抢劫当前节点：如果不抢劫当前节点，那么我们可以选择是否抢劫它的左右子节点。

状态定义：

对于每个节点 root，我们定义两个状态：
1. rob(root)：表示抢劫当前节点时能够获得的最大收益。
2. not_rob(root)：表示不抢劫当前节点时能够获得的最大收益。

状态转移方程：

如果抢劫当前节点：那么最大收益为当前节点的值 root.val 加上不抢劫左右子节点的收益：

rob(root) = root.val + not\_rob(root.left) + not\_rob(root.right)

如果不抢劫当前节点：那么最大收益为抢劫或不抢劫左右子节点中的最大值：

not\_rob(root) = \max(rob(root.left), not\_rob(root.left)) + \max(rob(root.right), not\_rob(root.right))

递归求解：

我们从树的根节点开始，递归地计算每个节点的抢劫和不抢劫情况下的最大收益。最终的结果是根节点抢劫和不抢劫情况下的最大值。

3. 解决方法

递归 + 动态规划方法

对于每个节点，使用递归来计算它的抢劫和不抢劫情况下的最大收益。
使用 postorder（后序遍历）的方式，先计算子节点的收益，再计算父节点的收益。
递归的终止条件是到达叶子节点的空节点，返回 (0, 0)，即抢劫和不抢劫的收益都是 0。

伪代码：

function rob(root):
    if root is None:
        return (0, 0)
    
    left = rob(root.left)
    right = rob(root.right)
    
    rob_current = root.val + left[1] + right[1]
    not_rob_current = max(left[0], left[1]) + max(right[0], right[1])
    
    return (rob_current, not_rob_current)

result = rob(root)
return max(result[0], result[1])

4. 进一步优化

空间优化：由于我们是通过递归的方式求解，每个节点只需要存储它左右子节点的结果，因此不需要额外的存储空间，空间复杂度可以保持在 O(h)，其中 h 是树的高度。
时间复杂度：时间复杂度为 O(n)，因为每个节点只被遍历一次。

5. 小总结

问题思路：通过动态规划自底向上的递归求解树中每个节点的最大收益。
递归的应用：后序遍历是解决树结构动态规划问题的常用方式，因为我们需要先计算子节点的结果，再计算父节点的结果。
时间复杂度：时间复杂度为 O(n)，适合处理大规模的二叉树输入。

以上就是打家劫舍 III问题的基本思路。

Python代码

class Solution:
    def rob(self, root: TreeNode) -> int:
        # 返回 (抢劫当前节点的最大收益, 不抢劫当前节点的最大收益)
        def helper(node):
            if not node:
                return (0, 0)
            
            left = helper(node.left)
            right = helper(node.right)
            
            # 抢劫当前节点的收益
            rob_current = node.val + left[1] + right[1]
            # 不抢劫当前节点的收益
            not_rob_current = max(left[0], left[1]) + max(right[0], right[1])
            
            return (rob_current, not_rob_current)
        
        # 计算根节点的抢劫与不抢劫的最大收益
        result = helper(root)
        # 返回两种情况中的最大值
        return max(result[0], result[1])

Python代码解释

递归定义：定义一个递归函数 helper(node)，返回两个值：抢劫当前节点的最大收益和不抢劫当前节点的最大收益。
状态转移：根据状态转移方程计算当前节点的最大收益。
返回结果：最终返回根节点抢劫和不抢劫情况下的最大值。

C++代码

class Solution {
public:
    pair<int, int> helper(TreeNode* node) {
        if (!node) return {0, 0};
        
        pair<int, int> left = helper(node->left);
        pair<int, int> right = helper(node->right);
        
        // 抢劫当前节点的最大收益
        int rob_current = node->val + left.second + right.second;
        // 不抢劫当前节点的最大收益
        int not_rob_current = max(left.first, left.second) + max(right.first, right.second);
        
        return {rob_current, not_rob_current};
    }
    
    int rob(TreeNode* root) {
        pair<int, int> result = helper(root);
        return max(result.first, result.second);
    }
};