LeetCode之打家劫舍 III（三百三十七）

目录

题目

解题

方法一、递归法

题目

 （原题链接：https://leetcode-cn.com/problems/house-robber-iii/）

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

示例 2:

解题

方法一、递归法

分析：这道其实就是一个二叉树，奇偶深度求和问题。

因此，我们可以假设

f(o)表示选择 o 节点的情况下，o节点的子树上被选择的节点的最大权值和；

g(o) 表示不选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和；

同时，L 和 R 代表 o节点的左右孩子。

这样就会得到两个关系式：

当 o 被选中时，o 的左右孩子都不能被选中，故 o 被选中情况下子树上被选中点的最大权值和为 L 和 R 不被选中的最大权值和相加，即 f(o)=g(R)+g(L)。

当 o 不被选中时，o 的左右孩子可以被选中，也可以不被选中。对于 o 的某个具体的孩子 x，它对 o 的贡献是 x 被选中和不被选中情况下权值和的较大值。故 g(o)=max{f(R),g(R)}+max{f(L),g(L)}。

梳理到这里就可以编码了，来看代码吧。

代码：（C++）

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * 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:
     
    
   

    

     

    
    

     
 unordered_map <TreeNode*, int> f, g;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 void dfs(TreeNode* o) {
     
    
   

    

     

    
    

     
 if (!o) {
     
    
   

    

     

    
    

     
 return;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       dfs(o->left);
     
    
   

    

     

    
    

     

       dfs(o->right);
     
    
   

    

     

    
    

     

       f[o] = o->val + g[o->left] + g[o->right]; // 偷o节点
     
    
   

    

     

    
    

     

       g[o] = max(f[o->left], g[o->left]) + max(f[o->right], g[o->right]); // 不偷o节点
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 int rob(TreeNode* o) {
     
    
   

    

     

    
    

     

       dfs(o);
     
    
   

    

     

    
    

     
 return max(f[o], g[o]);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      };
     
    
  
 

时间复杂度：O（logn）。

空间复杂度：O（1）。

执行结果：

文章来源: liuzhen.blog.csdn.net，作者：Data-Mining，版权归原作者所有，如需转载，请联系作者。

原文链接：liuzhen.blog.csdn.net/article/details/107825850