leetcode 337 打家劫舍III

﹏ヽ暗。殇╰゛Y 2022-08-28 03:51 100阅读 0赞

## 前言 ##

题目：[337. 打家劫舍 III][337. _ III]

参考题解：[打家劫舍 III-力扣官方题解][III-]

--------------------

## 提交代码 ##

二叉树的题目。考虑的时候，需要递归思考。即把树拆分成根，左子树，右子树。

这样思考之后，题目很容易有思路。思路见代码实现。

本题需要使用附加空间存储信息。否则，会超时。

另外，不要用脑袋瓜子去思考下面代码中的递归过程。按照只直觉的逻辑思路码代码就成。

class Solution {
    private:
        unordered_map<TreeNode*,int> record;
    public:
        int rob(TreeNode* root) {
            if(record[root])
                return record[root];
            if(root == nullptr)
                return 0;
            
            int steal_root = root->val;
            if(root->left) 
                steal_root = steal_root + rob(root->left->left) + rob(root->left->right);
            if(root->right)
                steal_root = steal_root + rob(root->right->left) + rob(root->right->right);
            
            int not_steal_root = rob(root->left) + rob(root->right);
    
            record[root] = max(steal_root,not_steal_root);
            return record[root];
        }
    };

[337. _ III]: https://leetcode-cn.com/problems/house-robber-iii/
[III-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.md

发表评论取消回复

表情：

评论列表（有 0 条评论，100人围观）

还没有评论，来说两句吧...

相关阅读

相关【动态规划】代码随想录算法训练营第四十七天 |198.打家劫舍，213.打家劫舍II ，337.打家劫舍III （待补充）

同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷...

梦里梦外;/ 2024年04月23日 04:31/ 0 赞/ 16 阅读

相关 337. 打家劫舍 III

题目： [337. 打家劫舍 III][337. _ III] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_sha

港控/mmm°/ 2022年11月26日 09:57/ 0 赞/ 115 阅读

相关 2021-04-04 | 337. 打家劫舍 III

1. 题目描述在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父

约定不等于承诺〃/ 2022年11月16日 15:15/ 0 赞/ 105 阅读

相关 House Robber III（C++打家劫舍 III）

(1)后序遍历，类似二叉树的公共祖先 / Definition for a binary tree node. struct TreeNode

太过爱你忘了你带给我的痛/ 2022年09月07日 15:54/ 0 赞/ 137 阅读

相关 leetcode 337 打家劫舍III

前言题目：[337. 打家劫舍 III][337. _ III] 参考题解：[打家劫舍 III-力扣官方题解][III-] --------------------

﹏ヽ暗。殇╰゛Y/ 2022年08月28日 03:51/ 0 赞/ 101 阅读

相关 [leetcode]337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entran

分手后的思念是犯贱/ 2022年08月22日 00:01/ 0 赞/ 93 阅读

相关 leetcode 337. House Robber III DP动态规划 + DFS深度有限遍历

The thief has found himself a new place for his thievery again. There is only one entran

旧城等待，/ 2022年06月07日 01:13/ 0 赞/ 113 阅读

相关 LeetCode198:打家劫舍

实验平台：[LeetCode][] 代码地址：[my github][] 题目描述： ![这里写图片描述][70] 示例： ![这里写图片描述][70 1]

小灰灰/ 2022年05月17日 21:27/ 0 赞/ 116 阅读

相关 LeetCode：337. House Robber III（偷窃问题）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

柔情只为你懂/ 2022年04月04日 12:54/ 0 赞/ 124 阅读

相关 337. House Robber III

一、题目　　1、审题　　　![746986-20190630160050060-269074321.png][] 　　2、分析　　　　给出一棵二叉树，取二叉树中的

阳光穿透心脏的1/2处/ 2021年11月02日 07:40/ 0 赞/ 172 阅读