337. House Robber III (Medium)

1.問題

• 小偷發現一個新的偷竊地點. 這地方只有一個出入口 "root", 除了"root"之外, 每間房子有一個parent house. 小偷懂了所有的房屋形成binary tree, 相鄰的房子的保全系統是相連的, 而且若相鄰的房子遭破壞時將會自通知警察

• 找出不被報警下可搶得的最大金額

2.想法

• Dynamic programming

  • 每回合要選擇可以賺最多錢的選項

    • 1.到前前node (left, right)為止所儲存錢 + 這一層的root node的錢

    • 2.到前node (left, right)為止所儲存錢 + 不加這一層的root node的錢

• DFS

3.程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        if (!root)
        {
            return 0;
        }
        int maxExcludeRoot = 0;
        return dfs(root, maxExcludeRoot);
    }
private:
        int dfs(TreeNode* root, int& maxExcludeRoot) {
            if (!root)
            {
                maxExcludeRoot = 0;
                return 0;
            }
            int maxExcludeRootRight = 0;
            int maxExcludeRootLeft = 0;
            //Caculate the max value of right, left subtree
            int maxLeft = dfs(root->left, maxExcludeRootLeft);
            int maxRight = dfs(root->right, maxExcludeRootRight);
            //maxIncludeRoot strored value that current value + max value in last last layer
            int maxIncludeRoot = root->val + maxExcludeRootLeft + maxExcludeRootRight;
            //maxExcludeRoot strored max value in last layer
            maxExcludeRoot = maxLeft + maxRight;
            return max(maxIncludeRoot, maxExcludeRoot);
        }
};

4.Performance