题目描述
思路解析
一句话答案：LeetCode 337 打家劫舍 III 是经典树形 DP：后序遍历让每个节点向父亲返回一对值——偷它的最大金额和不偷它的最大金额。偷它等于自身金额加左右孩子的不偷值；不偷它等于左右孩子各自两值取大再相加。根节点两值取大即答案，每个节点算一次，时间 O(n)、空间 O(h)。
树上打家劫舍在问什么
房子排成一棵二叉树，每个节点是一间房的金额，规则是不能同时偷有直接父子关系的两间房，求不触发报警能偷到的最大总额。注意约束只发生在相邻的父子之间：祖孙可以同偷，兄弟也可以同偷。它是一维打家劫舍（数组上不能偷相邻两间）从线性搬到树上的版本。
为什么子树只返回一个最大值不够用
自然的想法是写一个函数返回「这棵子树能偷到的最大金额」，父亲直接拿孩子的结果相加。但这个单一数值缺了关键信息：孩子的最优方案里，到底偷没偷孩子自己这个节点。父亲想偷自己时，必须保证两个孩子都没被偷，可孩子只报一个数字，父亲无从判断。硬要绕过去，就得去比较「偷根加上四个孙子的答案」和「不偷根加上两个孩子的答案」，同一棵子树被反复求解，不加记忆化会指数级爆炸。
症结在于孩子的答案依赖父亲的决策。破局的办法不是让父亲追问，而是让孩子把两种情况都算好、一起交上来。
状态怎么定义：每个节点一对值
给每个节点定义两个量：rob 表示偷这个节点时它整棵子树能得的最大金额，skip 表示不偷这个节点时的最大金额。转移只有两行：rob 等于自身金额加左孩子的 skip 加右孩子的 skip——偷了父亲，两个孩子被禁止偷，只能取它们的不偷档；skip 等于左孩子两值取大加右孩子两值取大——父亲不偷，孩子不受任何约束，各自挑对自己最优的档位。注意不偷父亲并不等于孩子必须偷，而是自由选择取较大者。
为什么这样递推是对的，为什么必须后序
正确性的依据是无后效性：父子间的约束只隔一层，一个节点的两个值只由左右孩子的两个值决定，与更上层的祖先怎么选完全无关。所以每棵子树的答案可以独立算好再上交，既不会漏也不会互相干扰。叶子是天然的边界：偷它等于自身金额，不偷它等于 0。
父亲要用到两个孩子的结果，就必须先算完孩子再算父亲——这正是后序遍历（左、右、根）的顺序。整棵树自底向上算到根，根节点 rob 与 skip 的较大者就是答案。
复杂度与常见错误
每个节点在后序中恰好被处理一次，做常数次加法和取大，时间 O(n)；递归栈深等于树高 h，平衡树 O(log n)，退化成链最坏 O(n)。
高频错误恰好对应两条转移各一个：偷父亲时误用了孩子的偷值——父子相邻不能同偷，必须配孩子的不偷档；不偷父亲时只取孩子的不偷值——孩子明明自由，应取两档中的较大者。第三个坑是函数只返回单个最大值，父亲缺料，整套递推立不起来。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这一对转移：偷父就逼孩子不偷，不偷父则孩子放开各取较大。自底向上算到根，取较大者就是答案。
后序遍历：先把左子树彻底算完，再右子树，最后才轮到父亲。每个节点会留下一条记录：它的 [偷它, 不偷它] 两个值。叶子最简单——偷=自身金额，不偷=0。
轮到节点 1（橙色）。它是叶子，没有孩子。偷它就拿自身金额，不偷它拿 0，所以左右孩子贡献都按 [0, 0] 处理。 这些值都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 1 算完（转绿）。偷它 = 自身 1 + 左不偷 0 + 右不偷 0 = 1（偷它就逼左右孩子不偷）。不偷它 = max(左偷 0, 左不偷 0) + max(右偷 0, 右不偷 0) = 0（孩子各取较大）。返回 [1, 0]，单看本节点更划算的是「偷它」。
轮到节点 2（橙色）。它是叶子，没有孩子。偷它就拿自身金额，不偷它拿 0，所以左右孩子贡献都按 [0, 0] 处理。 这些值都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 2 算完（转绿）。偷它 = 自身 2 + 左不偷 0 + 右不偷 0 = 2（偷它就逼左右孩子不偷）。不偷它 = max(左偷 0, 左不偷 0) + max(右偷 0, 右不偷 0) = 0（孩子各取较大）。返回 [2, 0]，单看本节点更划算的是「偷它」。
轮到节点 1（橙色）。它是叶子，没有孩子。偷它就拿自身金额，不偷它拿 0，所以左右孩子贡献都按 [0, 0] 处理。 这些值都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 1 算完（转绿）。偷它 = 自身 1 + 左不偷 0 + 右不偷 0 = 1（偷它就逼左右孩子不偷）。不偷它 = max(左偷 0, 左不偷 0) + max(右偷 0, 右不偷 0) = 0（孩子各取较大）。返回 [1, 0]，单看本节点更划算的是「偷它」。
轮到节点 3（橙色）。先读它两个孩子已经算好的返回值：左孩子 2 返回 [偷=2, 不偷=0]；右孩子 1 返回 [偷=1, 不偷=0]。 这些值都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 3 算完（转绿）。偷它 = 自身 3 + 左不偷 0 + 右不偷 0 = 3（偷它就逼左右孩子不偷）。不偷它 = max(左偷 2, 左不偷 0) + max(右偷 1, 右不偷 0) = 3（孩子各取较大）。返回 [3, 3]，单看本节点更划算的是「偷它」。
轮到节点 4（橙色）。先读它两个孩子已经算好的返回值：左孩子 1 返回 [偷=1, 不偷=0]；右孩子 3 返回 [偷=3, 不偷=3]。 这些值都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 4 算完（转绿）。偷它 = 自身 4 + 左不偷 0 + 右不偷 3 = 7（偷它就逼左右孩子不偷）。不偷它 = max(左偷 1, 左不偷 0) + max(右偷 3, 右不偷 3) = 4（孩子各取较大）。返回 [7, 4]，单看本节点更划算的是「偷它」。
轮到节点 6（橙色）。它是叶子，没有孩子。偷它就拿自身金额，不偷它拿 0，所以左右孩子贡献都按 [0, 0] 处理。 这些值都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 6 算完（转绿）。偷它 = 自身 6 + 左不偷 0 + 右不偷 0 = 6（偷它就逼左右孩子不偷）。不偷它 = max(左偷 0, 左不偷 0) + max(右偷 0, 右不偷 0) = 0（孩子各取较大）。返回 [6, 0]，单看本节点更划算的是「偷它」。
轮到节点 4（橙色）。先读它两个孩子已经算好的返回值：左孩子为空 → [0, 0]；右孩子 6 返回 [偷=6, 不偷=0]。 这些值都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 4 算完（转绿）。偷它 = 自身 4 + 左不偷 0 + 右不偷 0 = 4（偷它就逼左右孩子不偷）。不偷它 = max(左偷 0, 左不偷 0) + max(右偷 6, 右不偷 0) = 6（孩子各取较大）。返回 [4, 6]，单看本节点更划算的是「不偷它」。
轮到节点 1（橙色）。先读它两个孩子已经算好的返回值：左孩子为空 → [0, 0]；右孩子 4 返回 [偷=4, 不偷=6]。 这些值都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 1 算完（转绿）。偷它 = 自身 1 + 左不偷 0 + 右不偷 6 = 7（偷它就逼左右孩子不偷）。不偷它 = max(左偷 0, 左不偷 0) + max(右偷 4, 右不偷 6) = 6（孩子各取较大）。返回 [7, 6]，单看本节点更划算的是「偷它」。
轮到节点 5（橙色）。先读它两个孩子已经算好的返回值：左孩子为空 → [0, 0]；右孩子 1 返回 [偷=7, 不偷=6]。 这些值都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 5 算完（转绿）。偷它 = 自身 5 + 左不偷 0 + 右不偷 6 = 11（偷它就逼左右孩子不偷）。不偷它 = max(左偷 0, 左不偷 0) + max(右偷 7, 右不偷 6) = 7（孩子各取较大）。返回 [11, 7]，单看本节点更划算的是「偷它」。
轮到节点 3（橙色）。先读它两个孩子已经算好的返回值：左孩子 4 返回 [偷=7, 不偷=4]；右孩子 5 返回 [偷=11, 不偷=7]。 这些值都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 3 算完（转绿）。偷它 = 自身 3 + 左不偷 4 + 右不偷 7 = 14（偷它就逼左右孩子不偷）。不偷它 = max(左偷 7, 左不偷 4) + max(右偷 11, 右不偷 7) = 18（孩子各取较大）。返回 [14, 18]，单看本节点更划算的是「不偷它」。
全部算完，回到根节点 3：它返回 [偷=14, 不偷=18]。答案 = max(14, 18) = 18。这一棵树不偷根、把额度让给下面的孩子更划算——这就是逐节点权衡「偷它 vs 不偷它」自底向上汇总的结果。
空 / 单点 / 两层都被这套返回一对值的递归天然覆盖，无需特判。
认出「每个节点两态、自底向上、相邻不可同选」的模板，打家劫舍系列（线性 / 环形 / 树）就通了。
参考代码
class Solution: def rob(self, root): def dfs(node): if not node: return (0, 0) # (偷, 不偷) L = dfs(node.left) R = dfs(node.right) rob_it = node.val + L[1] + R[1] # 偷它→孩子不偷 skip_it = max(L) + max(R) # 不偷它→孩子各取大 return (rob_it, skip_it) return max(dfs(root))复杂度
- 时间：O(n)，每个节点后序访问一次，常数次运算
- 空间：O(h)，递归栈深度 = 树高 h，最坏（退化成链）O(n)
易错点
面试追问把动画讲成自己的话
追问为什么必须返回两个值，而不是只返回一个最大值？
追问它和一维「打家劫舍」（数组版）有什么联系？
追问为什么用后序遍历？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
把二叉搜索树转换为累加树
LeetCode 538 · 中等 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题