打家劫舍 III 图解题解

树上打家劫舍在问什么

房子排成一棵二叉树，每个节点是一间房的金额，规则是不能同时偷有直接父子关系的两间房，求不触发报警能偷到的最大总额。注意约束只发生在相邻的父子之间：祖孙可以同偷，兄弟也可以同偷。它是一维打家劫舍（数组上不能偷相邻两间）从线性搬到树上的版本。

为什么子树只返回一个最大值不够用

自然的想法是写一个函数返回「这棵子树能偷到的最大金额」，父亲直接拿孩子的结果相加。但这个单一数值缺了关键信息：孩子的最优方案里，到底偷没偷孩子自己这个节点。父亲想偷自己时，必须保证两个孩子都没被偷，可孩子只报一个数字，父亲无从判断。硬要绕过去，就得去比较「偷根加上四个孙子的答案」和「不偷根加上两个孩子的答案」，同一棵子树被反复求解，不加记忆化会指数级爆炸。

症结在于孩子的答案依赖父亲的决策。破局的办法不是让父亲追问，而是让孩子把两种情况都算好、一起交上来。

状态怎么定义：每个节点一对值

给每个节点定义两个量：rob 表示偷这个节点时它整棵子树能得的最大金额，skip 表示不偷这个节点时的最大金额。转移只有两行：rob 等于自身金额加左孩子的 skip 加右孩子的 skip——偷了父亲，两个孩子被禁止偷，只能取它们的不偷档；skip 等于左孩子两值取大加右孩子两值取大——父亲不偷，孩子不受任何约束，各自挑对自己最优的档位。注意不偷父亲并不等于孩子必须偷，而是自由选择取较大者。

为什么这样递推是对的，为什么必须后序

正确性的依据是无后效性：父子间的约束只隔一层，一个节点的两个值只由左右孩子的两个值决定，与更上层的祖先怎么选完全无关。所以每棵子树的答案可以独立算好再上交，既不会漏也不会互相干扰。叶子是天然的边界：偷它等于自身金额，不偷它等于 0。

父亲要用到两个孩子的结果，就必须先算完孩子再算父亲——这正是后序遍历（左、右、根）的顺序。整棵树自底向上算到根，根节点 rob 与 skip 的较大者就是答案。

复杂度与常见错误

每个节点在后序中恰好被处理一次，做常数次加法和取大，时间 O(n)；递归栈深等于树高 h，平衡树 O(log n)，退化成链最坏 O(n)。

高频错误恰好对应两条转移各一个：偷父亲时误用了孩子的偷值——父子相邻不能同偷，必须配孩子的不偷档；不偷父亲时只取孩子的不偷值——孩子明明自由，应取两档中的较大者。第三个坑是函数只返回单个最大值，父亲缺料，整套递推立不起来。

Python

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))

C++

class Solution {
    pair<int,int> dfs(TreeNode* node){
        if(!node) return {0, 0};            // {偷, 不偷}
        auto L = dfs(node->left);
        auto R = dfs(node->right);
        int robIt  = node->val + L.second + R.second;
        int skipIt = max(L.first,L.second) + max(R.first,R.second);
        return {robIt, skipIt};
    }
public:
    int rob(TreeNode* root){
        auto p = dfs(root);
        return max(p.first, p.second);
    }
};

Java

class Solution {
    public int rob(TreeNode root) {
        int[] r = dfs(root);
        return Math.max(r[0], r[1]);
    }
    // 返回长度 2 的数组：r[0]=偷它，r[1]=不偷它
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] L = dfs(node.left);
        int[] R = dfs(node.right);
        int robIt  = node.val + L[1] + R[1];   // 偷它→孩子不偷
        int skipIt = Math.max(L[0], L[1]) + Math.max(R[0], R[1]);
        return new int[]{robIt, skipIt};
    }
}