leetcode 337 打家劫舍III

﹏ヽ暗。殇╰゛Y 2022-08-28 03:51 141阅读 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 条评论，141人围观）

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

相关阅读

相关 ( “树” 之 DFS) 337. 打家劫舍 III ——【Leetcode每日一题】

337. 打家劫舍 III 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 `root`。除了 `root` 之外，每栋房子有且只有一个“父“房子

妖狐艹你老母/ 2024年03月23日 13:24/ 0 赞/ 45 阅读

相关 337. 打家劫舍 III（递归）

337. 打家劫舍 III 题目解题思路代码题目在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个

男娘i/ 2023年10月05日 17:48/ 0 赞/ 31 阅读

相关 [Leetcode][第337题][JAVA][打家劫舍3][递归][动态规划]

【问题描述】\[中等\] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6L

阳光穿透心脏的1/2处/ 2023年03月06日 05:19/ 0 赞/ 2 阅读

相关 337. 打家劫舍 III

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

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

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

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

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

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

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

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

相关 leetcode 337 打家劫舍III

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

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

相关 [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 赞/ 133 阅读

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

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

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

相关 337. House Robber III

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

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