LeetCode 337：打家劫舍 III（House Robber III）—— 题解 ✅

LeetCode 337：打家劫舍 III（House Robber III）—— 题解 ✅

📖 内容概要

在上次打家劫舍的基础上，小偷发现了一个新的可行区域：
二叉树结构的房屋。
如果直接相连的节点（父节点和子节点）在同一晚被闯入，系统会自动报警。

求在不触动警报的前提下，一夜之间能够偷窃到的最高金额。

✅ 树形 DP
✅ 后序遍历（自底向上）
✅ 打家劫舍系列第三题

💡 解题思路（核心）

一、关键难点

• 房屋不再是线性或环形
• 而是二叉树结构
• 父子节点不能同时偷

二、状态定义（非常关键）

对于以root为根的树，返回两个值：

res[0] = 不偷 root 时，子树的最大金额 res[1] = 偷 root 时，子树的最大金额

三、状态转移（树形 DP）

✅ 偷当前节点

val2=root.val+left[0]+right[0];

• 必须不能偷左右子节点

✅ 不偷当前节点

val1=max(left[0],left[1])+max(right[0],right[1]);

• 左右子树自由选择最优方案

四、递归 + 后序遍历

先计算左子树 再计算右子树 最后合并当前节点

✅ 自底向上
✅ 无重复计算

✅ AC 代码（Java）

/** * Definition for a binary tree node. */classTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}classSolution{publicintrob(TreeNoderoot){int[]res=help(root);returnMath.max(res[0],res[1]);}// 返回 [不偷当前节点的最大值, 偷当前节点的最大值]publicint[]help(TreeNoderoot){if(root==null){returnnewint[]{0,0};}int[]left=help(root.left);int[]right=help(root.right);// 不偷当前节点intval1=Math.max(left[0],left[1])+Math.max(right[0],right[1]);// 偷当前节点intval2=root.val+left[0]+right[0];returnnewint[]{val1,val2};}}

⏱️ 复杂度分析

🔍 打家劫舍三部曲对比

✅ 一句话总结

树形 DP = 后序遍历 + 每个节点返回“偷 / 不偷”两种状态的最大值。

📌 面试加分点（建议记住）

• ✅ 为什么返回数组而不是单个值？
• ✅ 为什么是后序遍历？
• ✅ 如何把树形 DP 抽象成状态机？
• ✅ 与记忆化搜索的关系