LeetCode 337 House Robber III：樹形 DP 打家劫舍進階解法

問題背景

小偷發現了一個新的作案區域，所有房屋構成一棵二叉樹（根節點為唯一入口）。若兩直接相連的房屋在同一晚被盜，會觸發報警。求在不觸發報警前提下，小偷能盜竊的最大金額。

核心思想：樹形動態規劃 + 狀態壓縮

對於每個節點，只有兩種決策：偷 或 不偷。這取決於其子節點的狀態。我們為每個節點維護兩個值：

• pre（不偷當前節點的最大收益）= 左子節點偷的收益 + 右子節點偷的收益
• curr（偷當前節點的最大收益）= 當前節點值 + 左子節點不偷的收益 + 右子節點不偷的收益

最終該節點的最大收益為 max(pre, curr)。

遞歸結構定義

struct Money {
    int pre;   // 不偷當前節點
    int curr;  // 偷當前節點
    Money() : pre(0), curr(0) {}
};

深度優先搜索實現

class Solution {
public:
    int rob(TreeNode* root) {
        Money res = dfs(root);
        return res.curr;  // 根節點的最大收益即為答案
    }

    Money dfs(TreeNode* root) {
        if (!root) return Money();
        
        Money left = dfs(root->left);
        Money right = dfs(root->right);
        
        Money cur;
        cur.pre = left.curr + right.curr;                    // 不偷：子節點必須偷
        cur.curr = max(cur.pre, root->val + left.pre + right.pre); // 偷：取不偷或偷的最大值
        return cur;
    }
};

關鍵點解析

1. 後序遍歷：先處理子節點，再根據子節點結果計算當前節點，自底向上構建答案。
2. 狀態轉移：pre 和 curr 互為依賴，完美體現了「相鄰節點不能同時選取」的約束。
3. 空間優化：僅使用遞歸棧空間 O(H)，無需額外數組。

複雜度

• 時間：O(N)，每個節點訪問一次。
• 空間：O(H)，遞歸棧深度，H 為樹高。

總結

本題是樹形 DP 的經典入門題。關鍵在於將「偷/不偷」抽象為兩個狀態，利用後序遍歷自底向上合併子問題答案。同類思想廣泛應用於「獨立集」「最大權重獨立集」等樹上優化問題。