树与图中等2 种解法

#337打家劫舍 III

房屋组成二叉树，父子节点不能同时选择，求最大金额。

#二叉树#动态规划#深度优先搜索

解题主线

记忆化递归中，选择当前节点时只能继续考虑孙子；不选时可考虑两个孩子。

树形 DP 对每个节点同时返回“不偷”和“偷”两种状态，一次后序遍历即可完成。

解法 1：记忆化递归

缓存每棵子树的最优答案，比较偷当前节点与不偷当前节点。

时间复杂度

O(n)

空间复杂度

O(n)，记忆表与递归栈

337. 打家劫舍 III · 记忆化递归

java

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

import java.util.HashMap;
import java.util.Map;

final class Solution {
    public int rob(TreeNode root) {
        return rob(root, new HashMap<>());
    }

    private int rob(TreeNode node, Map<TreeNode, Integer> memo) {
        if (node == null) return 0;
        Integer cached = memo.get(node);
        if (cached != null) return cached;

        int take = node.val;
        if (node.left != null) {
            take += rob(node.left.left, memo) + rob(node.left.right, memo);
        }
        if (node.right != null) {
            take += rob(node.right.left, memo) + rob(node.right.right, memo);
        }
        int skip = rob(node.left, memo) + rob(node.right, memo);
        int answer = Math.max(take, skip);
        memo.put(node, answer);
        return answer;
    }
}

缓存每棵子树的最优答案，比较偷当前节点与不偷当前节点。

解法 2：后序树形动态规划

每个节点返回 [skip, take]；父节点用两个孩子的状态直接合并。

时间复杂度

O(n)

空间复杂度

O(h)，递归栈；每层常数状态

337. 打家劫舍 III · 后序树形动态规划

java

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

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

    private int[] solve(TreeNode node) {
        if (node == null) return new int[2];
        int[] left = solve(node.left);
        int[] right = solve(node.right);
        int skip = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        int take = node.val + left[0] + right[0];
        return new int[] {skip, take};
    }
}

每个节点返回 [skip, take]；父节点用两个孩子的状态直接合并。

边界与易错点

记忆表应在每次公开调用中创建，避免跨不同树保留状态。
状态数组约定必须一致：这里 result[0] 表示不偷，result[1] 表示偷。
节点类型已内联，代码不再依赖旧仓库 base.TreeNode。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

medium/Q198_dp_robIII_337.java