【中等】力扣算法题解析LeetCode337：打家劫舍 III

关注文末推广名片，即可免费获得本题测试源码！

题目来源：LeetCode 337. 打家劫舍 III

问题抽象： 给定一个二叉树的根节点 root，表示房屋的布局（每个节点存储一个非负整数代表该房屋的金额），需计算在不触发警报的前提下可盗取的最大总金额。

1. 约束规则：

   • 盗取相邻节点会触发警报（即直接相连的父子节点不能同时被盗）；
   • 盗取节点需满足 树形拓扑约束：若节点被盗，其子节点及父节点均不可盗。

2. 优化目标：

   • 选择节点集合，使盗取金额总和最大化；
   • 节点选择需覆盖整棵树（任意节点可选或不选）。

3. 计算特性：

   • 需高效处理树形结构：通过递归遍历（如 DFS）计算子树最优解；
   • 状态分离：对每个节点维护 盗取/不盗取 两种状态的最优值。

4. 边界处理：

   • 空树（root = null）返回 0；
   • 单节点树直接返回该节点值；
   • 叶节点（无子节点）仅需考虑自身是否盗取；
   • 平衡树与倾斜树均需有效处理。

输入：二叉树根节点 root（节点数范围 [0, 10^4]，节点值范围 [0, 10^4]）
输出：最大可盗取金额（非负整数）。

解题思路

小偷需要在不触发警报（不能同时偷相邻父子节点）的前提下，在二叉树结构的房屋中偷窃最大金额。每个节点表示一个房屋，节点值代表金额。核心思路： 采用后序遍历（DFS）处理二叉树。对每个节点返回一个长度为2的数组：

• res[0]：不偷当前节点时，子树的最大偷窃金额
• res[1]：偷当前节点时，子树的最大偷窃金额

状态转移

1. 不偷当前节点：
   • 左右子节点可偷可不偷，取各自的最大值
   • res[0] = max(left[0], left[1]) + max(right[0], right[1])
2. 偷当前节点：
   • 左右子节点必须不偷
   • res[1] = node.val + left[0] + right[0]

时间复杂度：O(n)（每个节点只访问一次）。空间复杂度：O(n)（递归栈空间，树高最坏n）

代码实现（Java版）🔥点击下载源码

class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0}; // [不偷, 偷]
        }
        int[] left = dfs(node.left);
        int[] 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};
    }
}

代码说明

1. dfs()方法

   • 返回值：长度为2的数组，[0]表示不偷当前节点的最大收益，[1]表示偷当前节点的最大收益
   • 终止条件：节点为空时返回[0,0]
   • 递归逻辑：后序遍历获取左右子树状态，再计算当前节点状态

2. 状态计算

   • 不偷当前节点(notRob)：取左右子树各自的最大收益（偷或不偷均可）之和
   • 偷当前节点(rob)：当前节点值 + 左右子树不偷的收益

3. 主方法

   • 调用dfs(root)获取根节点状态
   • 返回偷与不偷根节点的最大值

提交详情（执行用时、内存消耗）