337.打家劫舍III

发表于： 分类于：
字数： 951 阅读：≈ 2分钟

🤡 337.打家劫舍III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

能够偷盗的房屋形成了一个二叉树

思路

基本思想

根据题中的描述，能够偷盗的房屋形成了一个二叉树，所以对于二叉树中的每一个节点，只有两种情况，要么偷要么不偷； 如果当前节点偷了，那么当前节点的孩子节点就不能偷，需要从孙子节点开始偷

如果当前节点没偷，那么当前节点的孩子节点就可以偷

从当前节点将遍历的路径分成了两条，两条路径上得到的金额不同，最终从当前节点出发得到的最大金额就是这两条路径得到的金额的较大者

对于程序来说，如果给定的二叉树是空树，此时直接返回0，如果给定的二叉树只有一个节点，那么直接偷，如果给定的二叉树从当前节点开始已经搜索过了，此时直接返回当前的答案供上面的节点使用

整体的遍历逻辑是：从上到下遍历，从下到上返回，最终返回从根节点出发的结果

执行流程

  1. 如果当前节点为空节点，返回0
  2. 如果当前节点没有孩子节点，直接返回当前节点的值
  3. 如果当前节点不为空且有孩子节点，且已经统计了从当前节点开始偷盗的结果，那么将当前的结果返回给上层作为参考
  4. 如果当前节点出发没有被统计，那么分为两种情况：
    1. 当前节点偷，那么下一次偷的只能是孙子节点开始
    2. 当前节点不偷，那么下一次偷的就可以是孩子节点开始
  5. 返回最终的答案

代码

根据以上分析，得出以下代码：

  1.  1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

    class Solution {
public: 
    //对于一棵树来说，当前节点只能是偷或者不偷
    //下层节点需要参考上层节点是不是偷
    //这个res记录了从那个节点开始偷能够获得的最大金额
    unordered_map<TreeNode*,int> res;
    int rob(TreeNode* root) {
        //第一个代码块
        {
            //确定递归的返回条件
            if(root==nullptr)
                return 0;
            if(root->left==nullptr&&root->right==nullptr)
                return root->val;
        }
        //第二个代码块
        {
            //当前节点被偷过了，直接返回
            if(res[root])
                return res[root];
            //当前节点没被偷过，此时需要分情况讨论
            else{
                //偷当前节点
                int val1=root->val;
                if(root->left!=nullptr)        
                    val1+=rob(root->left->left)+
                    		rob(root->left->right);
                if(root->right!=nullptr)
                    val1+=rob(root->right->left)+
                    	rob(root->right->right);

                //不偷当前节点
                int val2=rob(root->left)+rob(root->right);
                res[root]=max(val1,val2);
                return res[root];
            }
        }


    }
};

总结

主要是从当前节点出发，分成两种情况，从而形成两种不同的路径，从上到下遍历，从下到上返回结果