LeetCode 337. 打家劫舍 III

Categories:

题目描述
思路分析
1. 解法一：树形 DP（后序遍历）（推荐）
相似题目

题目描述

✅ 337. 打家劫舍 III

思路分析

解法一：树形 DP（后序遍历）（推荐）

核心思路：

本题是「打家劫舍」系列在二叉树上的变形，约束变为”相邻节点（父子关系）不能同时偷”。

对每个节点，有”偷”和”不偷”两种选择，需要递归子树的结果来决策。

朴素递归存在大量重复计算，优化方案是后序遍历时每个节点同时返回两个值：[rob, notRob]。

rob 表示偷当前节点可获得的最大金额，notRob 表示不偷当前节点可获得的最大金额。

状态转移：rob = node.val + left[1] + right[1]（偷当前，子节点必须不偷）；notRob = max(left[0], left[1]) + max(right[0], right[1])（不偷当前，子节点随意取最优）。

最终答案为根节点 max(rob, notRob)。

复杂度分析：

时间复杂度：O(n)，其中 n 表示二叉树的节点数，每个节点恰好访问一次。

空间复杂度：O(h)，其中 h 表示二叉树的高度，递归栈深度最坏为 O(n)，平均为 O(log n)。

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 rob = node.val + left[1] + right[1];
        // 不偷当前节点：子节点可偷可不偷，取最大值
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{rob, notRob};
    }
}

func rob(root *TreeNode) int {
	// dfs 返回两个状态：偷当前节点的最大值、不偷当前节点的最大值
	var dfs func(*TreeNode) (int, int)
	dfs = func(cur *TreeNode) (int, int) {
		if cur == nil {
			return 0, 0
		}
		// 递归计算左右子树的两种状态
		leftRob, leftNotRob := dfs(cur.Left)
		rightRob, rightNotRob := dfs(cur.Right)
		// 偷当前节点：左右子节点必须不偷
		robCur := cur.Val + leftNotRob + rightNotRob
		// 不偷当前节点：左右子节点各取最优
		notRobCur := max(leftRob, leftNotRob) + max(rightRob, rightNotRob)
		return robCur, notRobCur
	}

	resRob, resNotRob := dfs(root)
	return max(resRob, resNotRob)
}

相似题目

题目	难度	考察点
198. 打家劫舍	中等	动态规划
213. 打家劫舍 II	中等	动态规划、环形
740. 删除并获得点数	中等	动态规划
124. 二叉树中的最大路径和	困难	树形 DP、后序遍历
543. 二叉树的直径	简单	后序遍历两状态
968. 监控二叉树	困难	树形 DP 三状态
2246. 相邻字符不同的最长路径	困难	树形 DP、后序遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/99943604