337. 打家劫舍 III

思路

跟 98. 驗證二叉搜索樹 第二種寫法一樣，全域變數會紀錄最近被遞迴呼叫的函數存下來的結果。

• 當前節點選擇偷：左樹的根結點不能偷，右樹的根結點不能偷。
• 當前節點不偷：左樹根節點可偷可不偷；右樹根節點可偷可不偷。

各自選比較好的。

程式碼

全域變數法

class Solution {
public:
    int rob(TreeNode* root) {
        int yes, no; // 偷或不偷能偷到的最大金額
        auto dfs = [&](this auto&&dfs, TreeNode* node) -> void {
            if(!node) { // 空節點, 無法偷到東西, 設定為 0
                yes = 0;
                no = 0;
            }
            else {
                dfs(node->left); // 此時 yes, no 是左樹的 yes, no
                int leftYes = yes, leftNo = no;

                dfs(node->right);
                int rightYes = yes, rightNo = no; // 此時 yes, no 是左樹的 yes, no
                
                yes = node->val + leftNo + rightNo; // 這個節點偷, 那麼子節點都不能偷
                no = max(leftYes, leftNo) + max(rightYes, rightNo);// 這個節點不偷, 那麼子節點各自可偷可不偷
            }
        };
        dfs(root);
        return max(yes, no);
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(H)$，$H$是樹的高度