Medium

题目描述

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

提示：

  • 树的节点数在 [1, 10^4] 范围内
  • 0 <= Node.val <= 10^4

解题思路

这是一道经典的树形动态规划问题。关键在于理解约束条件：不能同时偷取直接相连的两个节点。

思路分析

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

  1. 偷当前节点：那么左右子节点都不能偷，只能偷左右子树的孙子节点
  2. 不偷当前节点：可以选择偷或不偷左右子节点，取最优解

解法一：递归 + 记忆化（基础思路）

直接递归会有重复计算问题，用哈希表缓存结果。

解法二：优化的树形DP（推荐）

为每个节点维护两个状态：

  • rob[0]：不偷当前节点的最大收益
  • rob[1]：偷当前节点的最大收益

状态转移方程：

  • rob[0] = max(left[0], left[1]) + max(right[0], right[1])
  • rob[1] = node.val + left[0] + right[0]

这种方法一次遍历即可，无需额外存储空间，是最优解法。

代码实现

class Solution {
public:
    int rob(TreeNode* root) {
        auto result = dfs(root);
        return max(result[0], result[1]);
    }
    
private:
    vector<int> dfs(TreeNode* node) {
        if (!node) return {0, 0};
        
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        
        int notRob = max(left[0], left[1]) + max(right[0], right[1]);
        int rob = node->val + left[0] + right[0];
        
        return {notRob, rob};
    }
};

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return [0, 0]
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            not_rob = max(left) + max(right)
            rob = node.val + left[0] + right[0]
            
            return [not_rob, rob]
        
        return max(dfs(root))

public class Solution {
    public int Rob(TreeNode root) {
        var result = Dfs(root);
        return Math.Max(result[0], result[1]);
    }
    
    private int[] Dfs(TreeNode node) {
        if (node == null) return new int[] {0, 0};
        
        var left = Dfs(node.left);
        var right = Dfs(node.right);
        
        int notRob = Math.Max(left[0], left[1]) + Math.Max(right[0], right[1]);
        int rob = node.val + left[0] + right[0];
        
        return new int[] {notRob, rob};
    }
}

var rob = function(root) {
    const dfs = (node) => {
        if (!node) return [0, 0];
        
        const left = dfs(node.left);
        const right = dfs(node.right);
        
        const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        const robCur = node.val + left[0] + right[0];
        
        return [notRob, robCur];
    };
    
    const result = dfs(root);
    return Math.max(result[0], result[1]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个节点只访问一次，n为节点数量
空间复杂度O(h)递归栈深度，h为树的高度，最坏情况O(n)

相关题目