337. House Robber III

Medium

Description

房屋排列成二元樹形狀，每個節點有一定金額。不能同時搶劫直接相連的兩個房屋（父子節點）。回傳在不觸發警報的情況下能搶到的最大金額。

Example:

Input: root = [3,2,3,null,3,null,1] Output: 7 Explanation: 3 + 3 + 1 = 7

Intuition#

每個節點有兩個狀態：搶或不搶，用後序遍歷自底向上決策。

如果搶當前節點，就不能搶左右子節點
如果不搶當前節點，左右子節點可搶可不搶（取最大值）
每個節點回傳兩個值：搶/不搶的最大收益

Approaches#

1: 遞迴 + HashMap 記憶化#

概念: 對每個節點計算搶與不搶的最大值，用 HashMap 避免重複計算
時間複雜度: O(n)
空間複雜度: 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: 後序遍歷回傳 Pair（搶/不搶）#

概念: 每個節點回傳 (搶的最大值, 不搶的最大值)，一次遍歷完成
時間複雜度: O(n)
空間複雜度: 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，每個節點維護多個狀態（搶/不搶），後序遍歷自底向上合併
關鍵技巧: 回傳 Pair 避免 HashMap 的開銷，且語義清晰；這是「樹形 DP」的經典模板