解題說明
House Robber III
題目描述： 所有房屋形成一棵二元樹，每個節點有一個金額。相鄰節點（直接相連的父子節點）不能同時被搶。求能搶到的最大金額。
解題思路： 使用樹形 DP。對每個節點，維護兩個狀態：
rob：搶劫此節點的最大收益 = 節點值 + 不搶左子的收益 + 不搶右子的收益notRob：不搶此節點的最大收益 = max(搶左子, 不搶左子) + max(搶右子, 不搶右子)
透過一次 DFS 後序遍歷，自底向上計算每個節點的兩個狀態。最終答案為根節點的 max(rob, notRob)。
這避免了記憶化遞迴中對同一子樹的重複計算，每個節點只訪問一次。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個節點恰好訪問一次，每次做 O(1) 計算。
空間複雜度：O(h) — h 為樹的高度，遞迴堆疊深度。最壞情況（鏈狀樹）為 O(n)，平衡樹為 O(log n)。
虛擬碼
1. Define dfs(node) -> (rob_value, not_rob_value): a. If node is null, return (0, 0) b. (rob_left, not_rob_left) = dfs(node.left) c. (rob_right, not_rob_right) = dfs(node.right) d. rob_this = node.val + not_rob_left + not_rob_right e. not_rob_this = max(rob_left, not_rob_left) + max(rob_right, not_rob_right) f. Return (rob_this, not_rob_this) 2. (rob_root, not_rob_root) = dfs(root) 3. Return max(rob_root, not_rob_root)
其他解法
記憶化遞迴（HashMap）：對每個節點計算「搶此節點」和「不搶此節點」的最大值，用 HashMap 快取已計算的節點。時間 O(n)，空間 O(n)（HashMap + 遞迴）。相比 pair 返回值的方法，需要額外的雜湊表空間，且常數倍較大。
暴力遞迴：對每個節點，分「搶」和「不搶」兩種決策遞迴計算。不搶時取子節點的最大值，搶時取孫節點的最大值。時間 O(2^n) 指數級，大量重複計算。僅適合理解問題結構，不可用於實際提交。
延伸思考
- House Robber I（LeetCode 198）是線性陣列版本，如何從一維 DP 推廣到樹形 DP？
- House Robber II（LeetCode 213）是環形陣列版本，與樹形版本在處理「相鄰」約束時有何不同？
- 若每個節點可以選擇搶或不搶，但限制不是父子，而是「距離 <= k」的節點不能同時搶，如何修改算法？