337. House Robber III

──────────────────────────────────────────────────────────────────────

這一題是 198. House Robber 和 213. House Robber II 的延伸題組，題目的情境相同，但是做法完全不同，是一題後序遍歷的問題。

房子排成一棵二元樹，父子節點不能同時被偷，求最大獲利。

思路

198 的房子排成一排、213 排成一環，這題排成一棵樹。「相鄰」的定義變成「父子關係」，於是一維的 dp[i] 沒地方放了 —— 樹沒有線性的索引。

換成「遞迴回傳什麼」來想

樹的 DP 不用 dp 陣列，改用遞迴的回傳值當狀態。所以問題變成：每個節點要回報給父節點什麼資訊，父節點才算得出自己的答案？

只回報「這棵子樹的最大獲利」是不夠的。因為父節點要做決定時需要知道：

我要偷自己 → 兩個子節點都不能偷，我需要「子樹在根不被偷的前提下的最大獲利」
我不偷自己 → 子節點偷不偷都可以，我需要「子樹的最大獲利」

一個數字回答不了兩個問題，所以回傳一對值：

(rob, not_rob) = (偷這個節點時，這棵子樹的最大獲利,
                  不偷這個節點時，這棵子樹的最大獲利)

有了這對值，轉移式就自己浮出來了：

r o b = n o d e . v a l + l e f t_{n o t R o b} + r i g h t_{n o t R o b}

n o t R o b = \max (l e f t_{r o b}, l e f t_{n o t R o b}) + \max (r i g h t_{r o b}, r i g h t_{n o t R o b})

注意 not_rob 是兩邊各自取 max，不是直接用 rob。 我不偷自己時，子節點「可以」偷但不是「必須」偷 —— 有些情況不偷子節點反而更好（例如子節點值很小、但孫節點很大）。這是這題最常見的錯誤。

必須等左右子樹都算完才能算自己 → 後序遍歷。這正是 Tree 遍歷模板裡「後序型：回傳值就是這棵子樹的答案」那一型的典型例子。

為什麼不能只回傳一個值

如果每個節點只回傳「子樹最大獲利」，父節點拿到之後無從得知那個最大值有沒有用到子節點自己 —— 也就不知道自己還能不能偷。這種「答案不夠、要多帶一個維度上來」的情況在樹形 DP 很常見，124. Binary Tree Maximum Path Sum 是另一個例子（那題是回傳值和答案本身不一樣）。

解題方向

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:

        def helper(node):
            if not node:
                return (0, 0)
            left = helper(node.left)
            right = helper(node.right)

            rob = node.val + left[1] + right[1]
            not_rob = max(left) + max(right)

            return rob, not_rob

        return max(helper(root))

約定是 tuple 的第 0 項是「偷」、第 1 項是「不偷」，所以：

left[1] 是「左子樹的根不被偷」的最大獲利 —— 我偷自己時要用這個
max(left) 是「左子樹隨便」的最大獲利 —— 我不偷自己時用這個

max(left) 這個寫法很簡潔（直接對 tuple 取 max），但也容易讓人看不出語意。想清楚一點可以寫成 max(left[0], left[1])。

空節點回傳 (0, 0) 是自然的 base case：沒有節點，偷不偷都是 0。

最後 max(helper(root)) 對根節點的兩個選項取大 —— 根節點沒有父節點，所以偷不偷都可以。

這個解法不需要記憶化。 每個節點只被 helper 呼叫一次，資訊沿著樹往上傳一趟就結束了。有些人會寫成 rob(node) 遞迴呼叫 rob(孫節點) 那種形式，那才需要 memo（否則會重複計算孫節點）—— 回傳一對值的寫法從結構上就避開了重複。

補充

整個家族：

題目	排列方式	「相鄰」是什麼	解法
198. House Robber	一排	陣列上相鄰	一維 DP
213. House Robber II	一環	首尾也相鄰	拆成兩條直線各跑一次
337 這題	一棵樹	父子相鄰	後序遞迴，回傳 (偷, 不偷) 兩個值
740. Delete and Earn	一排（按數值）	數值差 1	先轉換，再套 198

回傳多個狀態的其他樹形 DP：124. Binary Tree Maximum Path Sum、543. Diameter of Binary Tree。共同點都是「回傳給父節點的東西，和最終答案不是同一件事」，見 Tree 遍歷模板。

複雜度

時間 $O (n)$ — 每個節點只被造訪一次，每次做常數次計算
空間 $O (h)$ — 遞迴堆疊，h 是樹高

其中 n 是節點數、h 是樹高（平衡樹 $O (\log n)$ 、退化成鏈時 $O (n)$ ）。

不需要額外的 memo，這是回傳一對值這個設計最漂亮的地方 —— 用資料結構解決了重複計算，而不是用快取。