房屋排列成二元樹形狀，每個節點有一定金額。不能同時搶劫直接相連的兩個房屋（父子節點）。回傳在不觸發警報的情況下能搶到的最大金額。
Example:
Input: root = [3,2,3,null,3,null,1] Output: 7 Explanation: 3 + 3 + 1 = 7
Intuition
TIP
每個節點有兩個狀態：搶或不搶，用後序遍歷自底向上決策。
- 如果搶當前節點，就不能搶左右子節點
- 如果不搶當前節點，左右子節點可搶可不搶（取最大值）
- 每個節點回傳兩個值：搶/不搶的最大收益
Approaches
1. Recursion + HashMap Memoization — O(n) / O(n)
- Idea: 對每個節點計算搶與不搶的最大值，用 HashMap 避免重複計算
- Time:
O(n) - Space:
O(n)
class Solution {
private val memo = HashMap<TreeNode, Int>()
fun rob(root: TreeNode?): Int {
if (root == null) return 0
memo[root]?.let { return it }
// 搶當前節點
var robCurrent = root.`val`
root.left?.let {
robCurrent += rob(it.left) + rob(it.right)
}
root.right?.let {
robCurrent += rob(it.left) + rob(it.right)
}
// 不搶當前節點
val skipCurrent = rob(root.left) + rob(root.right)
val result = maxOf(robCurrent, skipCurrent)
memo[root] = result
return result
}
}⭐ 2. Postorder Returning Pair (rob/skip) — O(n) / O(h)
- Idea: 每個節點回傳 (搶的最大值, 不搶的最大值)，一次遍歷完成
- Time:
O(n) - Space:
O(h)，h 為樹高
class Solution {
fun rob(root: TreeNode?): Int {
val (robIt, skipIt) = dfs(root)
return maxOf(robIt, skipIt)
}
// 回傳 Pair(搶此節點的最大值, 不搶此節點的最大值)
private fun dfs(node: TreeNode?): Pair<Int, Int> {
if (node == null) return 0 to 0
val (leftRob, leftSkip) = dfs(node.left)
val (rightRob, rightSkip) = dfs(node.right)
val robCurrent = node.`val` + leftSkip + rightSkip
val skipCurrent = maxOf(leftRob, leftSkip) + maxOf(rightRob, rightSkip)
return robCurrent to skipCurrent
}
}🔑 Takeaways
- Pattern: 樹上 DP，每個節點維護多個狀態（搶/不搶），後序遍歷自底向上合併
- Key trick: 回傳 Pair 避免 HashMap 的開銷，且語義清晰；這是「樹形 DP」的經典模板