---
title: "337. House Robber III"
url: "https://laigary.com/interview/coding/337-house-robber-iii"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Tree", "Dynamic Programming", "Postorder Traversal", "Classic"]
---

# 337. House Robber III

[337\. House Robber III](https://leetcode.com/problems/house-robber-iii/)

這一題是 [198. House Robber](/interview/coding/198-house-robber) 和 [213. House Robber II](/interview/coding/213-house-robber-ii) 的延伸題組，題目的情境相同，但是做法完全不同，是一題後序遍歷的問題。

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

## 思路

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

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

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

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

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

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

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

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

$$
rob = node.val + left_{notRob} + right_{notRob}
$$

$$
notRob = \max(left_{rob},\, left_{notRob}) + \max(right_{rob},\, right_{notRob})
$$

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

必須等左右子樹都算完才能算自己 → **後序遍歷**。這正是 [Tree 遍歷模板](/interview/coding/tree-traversal-template) 裡「後序型：回傳值就是這棵子樹的答案」那一型的典型例子。

### 為什麼不能只回傳一個值

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

## 解題方向

```python
# 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](/interview/coding/198-house-robber) | 一排 | 陣列上相鄰 | 一維 DP |
| [213. House Robber II](/interview/coding/213-house-robber-ii) | 一**環** | 首尾也相鄰 | 拆成兩條直線各跑一次 |
| **337 這題** | 一棵**樹** | 父子相鄰 | **後序遞迴，回傳 (偷, 不偷) 兩個值** |
| [740. Delete and Earn](/interview/coding/740-delete-and-earn) | 一排（按**數值**） | 數值差 1 | 先轉換，再套 198 |

**回傳多個狀態的其他樹形 DP**：[124. Binary Tree Maximum Path Sum](/interview/coding/124-binary-tree-maximum-path-sum)、[543. Diameter of Binary Tree](/interview/coding/543-diameter-of-binary-tree)。共同點都是「**回傳給父節點的東西，和最終答案不是同一件事**」，見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

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

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

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