LeetCode 337打家劫舍 IIIHouse Robber III—— 题解 ✅ 内容概要在上次打家劫舍的基础上小偷发现了一个新的可行区域二叉树结构的房屋。如果直接相连的节点父节点和子节点在同一晚被闯入系统会自动报警。求在不触动警报的前提下一夜之间能够偷窃到的最高金额。✅ 树形 DP✅ 后序遍历自底向上✅ 打家劫舍系列第三题 解题思路核心一、关键难点房屋不再是线性或环形而是二叉树结构父子节点不能同时偷二、状态定义非常关键对于以root为根的树返回两个值res[0] 不偷 root 时子树的最大金额 res[1] 偷 root 时子树的最大金额三、状态转移树形 DP✅ 偷当前节点val2root.valleft[0]right[0];必须不能偷左右子节点✅ 不偷当前节点val1max(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.valval;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.valval;this.leftleft;this.rightright;}}classSolution{publicintrob(TreeNoderoot){int[]reshelp(root);returnMath.max(res[0],res[1]);}// 返回 [不偷当前节点的最大值, 偷当前节点的最大值]publicint[]help(TreeNoderoot){if(rootnull){returnnewint[]{0,0};}int[]lefthelp(root.left);int[]righthelp(root.right);// 不偷当前节点intval1Math.max(left[0],left[1])Math.max(right[0],right[1]);// 偷当前节点intval2root.valleft[0]right[0];returnnewint[]{val1,val2};}}⏱️ 复杂度分析指标复杂度时间复杂度O(n)每个节点只访问一次空间复杂度O(h)递归栈h 为树高 打家劫舍三部曲对比题目结构解法198线性街道一维 DP213环形拆环为链337二叉树树形 DP✅ 一句话总结树形 DP 后序遍历 每个节点返回“偷 / 不偷”两种状态的最大值。 面试加分点建议记住✅ 为什么返回数组而不是单个值✅ 为什么是后序遍历✅ 如何把树形 DP 抽象成状态机✅ 与记忆化搜索的关系