打家劫舍 III 图解题解

这道题到底在问什么

root

[3,2,3,null,3,null,1]

输出

7

最优解：一步一步想明白

1. 3有人想：偶数层全偷、奇数层全不偷，二选一取大。但局部结构千变万化，这种「整层一刀切」常常不是最优，必须逐户决策。
2. 4难点在于：父亲偷不偷，取决于孩子偷没偷。所以每个节点不返回一个数，而是返回一对：左边是「不偷我」的最大值，右边是「偷我」的最大值。
3. 5约定每户回传一对账 (不偷, 偷)树形 DP 一律后序：先递归到底，把孩子的账算出来，父亲才有依据。我们从最底下两个叶子开始：值为 3 的那户，和值为 1 的那户。
4. 6叶子3 回传 (不偷 0, 偷 3)　叶子1 回传 (不偷 0, 偷 1)叶子没有孩子。偷它，就赚它自己的钱；不偷它，赚 0。所以左边那户 3 回传 (0, 3)，右边那户 1 回传 (0, 1)。这就是递归的底。
5. 7父=2　偷它 = 2 + 左孩子不偷0 + 右孩子不偷0 = 2看值为 2 的这户。它左孩子是空、右孩子是那户 3。如果偷它，相邻的孩子就一律不能偷，只能取孩子那对里「不偷」的数：2 加 0 加 0，偷它只赚 2。
6. 8父=2　不偷它 = max(0,0) + max(0,3) = 0 + 3 = 3如果不偷这户 2，孩子就解放了：每个孩子在自己那对里随便挑大的。左边空取 0，右边那户 3 偷它更划算取 3。不偷它反而能赚 3。所以这户 2 回传 (不偷3, 偷2)。
7. 9父=3　偷=3+0+0=3　不偷=max(0,0)+max(0,1)=1　回传 (不偷1, 偷3)对右子树重复同一套：值为 3 的这户，偷它配孩子不偷得 3；不偷它让孩子 1 自己挑大的得 1。它回传 (不偷1, 偷3)。注意偷它 3 比不偷它 1 更优。
8. 10根=3　左回传(3,2)　右回传(1,3)回到根 3。它两个孩子的账已经备好：左孩子 (不偷3, 偷2)、右孩子 (不偷1, 偷3)。偷根时孩子都不能动，取它们的「不偷」：3 加 3 加 1 等于 7。
9. 11不偷根 = max(3,2) + max(1,3) = 3 + 3 = 6　答案 = max(6,7) = 7不偷根时，两个孩子各挑大的：左取 max(3,2)=3、右取 max(1,3)=3，合计 6。根回传 (不偷6, 偷7)。最后在根这对里取大的：max(6,7) 等于 7，正是答案。
10. 14一句话本质：偷我，就只能要孩子的「不偷」；不偷我，孩子各自挑大的。把这对账往上传，根那一对里取大的就是答案。
11. 16右孩子若只用「偷3」而非 max(1,3)，碰巧也对；换成一条链 4→1→2→3 就翻车换条链 4 到 1 到 2 到 3。不偷根 4 时，孩子 1 那条线如果机械地偷孩子，反而错过更值钱的孙子。必须让孩子在「偷 / 不偷」里取大，才能把深处的钱捞上来。
12. 20学会「每个节点回传一对状态」后，二叉树最大路径和、监控二叉树都是同一套：先想清每个节点要向上汇报哪几种状态，再写后序合并。点开树专题，让小欧带你把这套迁移练熟。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def rob(self, root):
        def dfs(node):
            if not node:
                return (0, 0)        # (不偷, 偷)
            l_skip, l_rob = dfs(node.left)
            r_skip, r_rob = dfs(node.right)
            rob_it = node.val + l_skip + r_skip
            skip_it = max(l_skip, l_rob) + max(r_skip, r_rob)
            return (skip_it, rob_it)
        return max(dfs(root))

class Solution {
    pair<int,int> dfs(TreeNode* node) {  // {skip, rob}
        if (!node) return {0, 0};
        auto [lSkip, lRob] = dfs(node->left);
        auto [rSkip, rRob] = dfs(node->right);
        int robIt = node->val + lSkip + rSkip;
        int skipIt = max(lSkip, lRob) + max(rSkip, rRob);
        return {skipIt, robIt};
    }
public:
    int rob(TreeNode* root) {
        auto [skip, rob] = dfs(root);
        return max(skip, rob);
    }
};

class Solution {
    // 返回 {不偷, 偷}
    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[0] + r[0];
        int skipIt = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{skipIt, robIt};
    }
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }
}

def dfs(node):
    if not node:
        return ____            # 1. 空节点的初始状态
    left  = dfs(node.left)     # 2. 后序：先拿孩子的账
    right = dfs(node.right)
    选它   = node.val + 左孩子不选 + 右孩子不选
    不选它 = max(左两态) + max(右两态)  # 3. 合并
    return (不选它, 选它)        # 4. 向上回传整组状态

pair<int,int> dfs(TreeNode* node) {
    if (!node) return ____;                 // 1. 空节点初始态
    auto L = dfs(node->left);               // 2. 后序拿孩子
    auto R = dfs(node->right);
    int take = node->val + L.first + R.first;
    int skip = max(L.first,L.second)+max(R.first,R.second); // 3. 合并
    return {skip, take};                    // 4. 回传整组
}

int[] dfs(TreeNode node) {
    if (node == null) return ____;          // 1. 空节点初始态
    int[] L = dfs(node.left);               // 2. 后序拿孩子
    int[] R = dfs(node.right);
    int take = node.val + L[0] + R[0];
    int skip = Math.max(L[0],L[1]) + Math.max(R[0],R[1]); // 3. 合并
    return new int[]{skip, take};           // 4. 回传整组
}

复杂度

面试官可能追问