树与图中等2 种解法
#337打家劫舍 III
房屋组成二叉树，父子节点不能同时选择，求最大金额。
#二叉树#动态规划#深度优先搜索
原题
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 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, 104]范围内 0 <= Node.val <= 104
解题主线
- 记忆化递归中，选择当前节点时只能继续考虑孙子；不选时可考虑两个孩子。
- 树形 DP 对每个节点同时返回“不偷”和“偷”两种状态，一次后序遍历即可完成。
解法 1：记忆化递归
缓存每棵子树的最优答案，比较偷当前节点与不偷当前节点。
-
时间复杂度： O(n)
-
空间复杂度： O(n)，记忆表与递归栈
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)，递归栈；每层常数状态
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) {
// 空子树在“不偷”和“偷”两种语义下贡献均为 0。
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};
}
}边界与易错点
- 记忆表应在每次公开调用中创建，避免跨不同树保留状态。
- 状态数组约定必须一致：这里 result[0] 表示不偷，result[1] 表示偷。
- 节点类型已内联，代码不再依赖旧仓库 base.TreeNode。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q198_dp_robIII_337.java