###### tags: `LeetCode` `Recursion` `Tree` `Medium` `DFS`
# LeetCode #337 [House Robber III](https://leetcode.com/problems/house-robber-iii/)
### (Medium)

在上次打劫完一條街道之後和一圈房屋後，小偷又發現了一個新的可行竊的地區。這個地區只有一個入口，我們稱之為“根”。除了“根”之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之後，聰明的小偷意識到“這個地方的所有房屋的排列類似於一棵二元樹”。如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。

計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。

---
每個節點都會回傳一組數組{with root, without root}代表搶劫該節點可獲得的最大利潤,以及不搶劫該節點可獲得的最大利潤。

同樣的, 以DFS方式先處理最底層節點, 並一次回傳, 最後回傳搶劫根結點與不搶劫根結點中利潤較大者。

class Solution {
public:
    int rob(TreeNode* root) {
        return max(tryrob(root)[0],tryrob(root)[1]);
    }
    vector<int> tryrob(TreeNode* node){
        //{with root, without root}
        if(!node)return {0,0};
        vector<int> left=tryrob(node->left);
        vector<int> right=tryrob(node->right);
        vector<int> nodeval(2);
        nodeval[0]=left[1]+right[1]+node->val;//with root
        nodeval[1]=max(left[0],left[1])+max(right[0],right[1]);//without root
        return nodeval;
    }
};

---
LeetCode版本

核心概念相似, 只是利用參考的特性, 省去記憶體空間, 計算速度也更快。

class Solution {
public:
    int tryRob(TreeNode* root, int& l, int& r) {
        if (!root)
            return 0;
            
        int ll = 0, lr = 0, rl = 0, rr = 0;
        l = tryRob(root->left, ll, lr);
        r = tryRob(root->right, rl, rr);
        
        return max(root->val + ll + lr + rl + rr, l + r);
    }

    int rob(TreeNode* root) {
        int l, r;
        return tryRob(root, l, r);
    }
};