LeetCode 337 House Robber III：從錯誤嘗試到正確樹形 DP 的思維轉折

題目回顧

同 2558，房屋構成二叉樹，相鄰節點不可同時選取，求最大權重和。

一個直觀但錯誤的想法：按層奇偶性求和

許多初學者（包括本文作者）會想：「二叉樹的相鄰節點必定一奇一偶層，直接比較奇數層總和與偶數層總和取最大值不就行了？」

// 錯誤代碼示例：BFS 按層累加
int rob(TreeNode* root) {
    if (!root) return 0;
    queue q;
    q.push(root);
    int oddSum = root->val, evenSum = 0;
    int level = 2;
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; ++i) {
            TreeNode* node = q.front(); q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
            if (level % 2) oddSum += node->val;
            else evenSum += node->val;
        }
        ++level;
    }
    return max(oddSum, evenSum);
}

為什麼這是錯的？

反例：
根節點值 100，左子節點 1，右子節點 1。
奇數層和 = 100，偶數層和 = 2。
但最優解是偷兩個子節點（1+1=2）還是偷根節點（100）？顯然偷根節點更好。但若根節點值 3，左右子節點均為 4？
奇數層和 = 3，偶數層和 = 8。最優解確為 8。
關鍵缺陷：奇偶層劃分強制要求「要么全選奇數層，要么全選偶數層」，但實際最優解可能在同一層中「選一些，不選另一些」。例如：某層有節點 A(100) 和 B(1)，最優解可能只選 A 不選 B，但奇偶層法會強制兩者同選同不選。

正確解法：樹形 DP（狀態壓縮版）

參考網友高票解法，定義遞歸函數返回 pair 或兩個引用參數：

• child：偷當前節點的收益
• childchild：不偷當前節點的收益

int rob(TreeNode* root) {
    int child = 0, childchild = 0;
    dfs(root, child, childchild);
    return max(child, childchild);
}

void dfs(TreeNode* root, int& child, int& childchild) {
    if (!root) return;
    int l1 = 0, l2 = 0, r1 = 0, r2 = 0;
    dfs(root->left, l1, l2);   // l1=偷左子，l2=不偷左子
    dfs(root->right, r1, r2);  // r1=偷右子，r2=不偷右子
    
    child = l2 + r2 + root->val;           // 偷當前：子節點必不偷
    childchild = max(l1, l2) + max(r1, r2); // 不偷當前：子節點可偷可不偷，取最大
}

兩種 DP 寫法的對比

總結

本文記錄了從「按層貪心」到「樹形 DP」的思維糾錯過程。樹上相鄰約束問題，本質是「獨立集」問題，必須用 DP 而非貪心。狀態定義為「偷/不偷」或「選/不選」是通用範式，值得熟練掌握。