题解 | #打家劫舍(三)#

打家劫舍(三)

题目描述

你是一个经验丰富的小偷，经过上次在街边和湖边得手后你准备挑战一次自己，你发现了一个结构如二叉树的小区，小区内每个房间都存有一定现金，你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。 问，给定一个二叉树结构的小区，如之前两次行动一样，你无法在不触动警报的情况下同时偷窃两个相邻的房间，在不触动警报的情况下最多的偷窃金额。

方法一：递归法

解题思路

对于本题目的求解，使用递归搜索的方法进行，对于每次选择的位置，如果选定当前位置，那么下一层递归的值不可选，如果不选择当前位置，那么下层递归的值可选。在递归过程中记录最大值，最后输出即可。

解题代码

class Solution {
public:
    int dfs(TreeNode* r,bool pick = true)
    { // 当前是否可选
        if(r == NULL)return 0;
        // 当前不选
        int ans = dfs(r->left) + dfs(r->right);
        // 选择当前
        if(pick){
            ans = max(ans, r->val + dfs(r->left,false) + dfs(r->right,false));
        }
        return ans;
    }
    int rob(TreeNode* root)
    {
        return dfs(root);
    }
};

复杂度分析

时间复杂度：最坏情况为尝试了所有的组合，因此时间复杂度为$O(2^n)O(2^n)$。

空间复杂度：使用递归，且深度不超过树的高度，因此空间复杂度为$O(logn)O(logn)$

方法二：优化的方法

解题思路

基于方法一，在处理下层结果时，对同样的内容反复计算，因此用节点指针和选择状态来保存结果，减少重复计算。

解题代码

class Solution {
public:
    int dfs(map<pair<TreeNode*,int>,int >& state,TreeNode* r,bool pick = true){ // 当前是否可选
        if(r == NULL)return 0;
        if(state.count({r,pick})) return state[{r,pick}]; //  计算过 不重复计算直接返回结果
        // 当前不选
        int ans = dfs(state,r->left) + dfs(state, r->right); // 递归下降
        // 选择当前
        if(pick)
        {
            ans = max(ans, r->val + dfs(state, r->left,false) + dfs(state, r->right,false)); // 递归下降
        }
        return state[{r,pick}] = ans; // 记录结果并返回
    }
    int rob(TreeNode* root) {
        map<pair<TreeNode*,int>,int > state = {}; // 状态记录, 键为 节点和选择状态
        return dfs(state, root);
    }
};

复杂度分析

时间复杂度：递归+优化，因此时间复杂度为$O(n)O(n)$。

空间复杂度：使用map申请内存地址空间，因此空间复杂度为$O(n)O(n)$