力扣（LeetCode)每日一题 337. 打家劫舍 III

水深无声 2024-03-02 08:26 43阅读 0赞

题目链接[https://leetcode.cn/problems/house-robber-iii/description/?envType=daily-question&envId=2023-09-18][https_leetcode.cn_problems_house-robber-iii_description_envType_daily-question_envId_2023-09-18]

分析：当层数非常多时：具体情况分为下边三大类

![cdfe01f916c94c1593ba81655c0b9f93.png][]

**再细分为两种情况：1.要么根节点被偷（图中情况一），2.要么根节点的一个或两个孩子被偷（图中情况二三）。**

于是我写出了如下代码，，

class Solution {
        public int rob(TreeNode root) {
            if(root==null){
                return 0;
            }
            int res1=root.val;
            if(root.left!=null){
                res1 += rob(root.left.left) + rob(root.left.right);
            }
            if(root.right!=null){
                res1 += rob(root.right.right) + rob(root.right.left);
            }
            int res2 = 0;
            res2 = rob(root.left) + rob(root.right);
            return Math.max(res1,res2);
        }
    }

![6ec4fb80ec584ad7ad3f255103e04027.png][]

结果发现超时了，，然后打开 房建斌学算法 大佬的讲解。

超时的原因：根节点的孙子被重复计算了，（三辈份：爷爷 父亲 孙子 —— 爷爷需要计算一次父亲计算一次孙子，父亲计算一次孙子，孙子辈被计算了2次）于是时间耗费太多了。

**大佬的讲解十分详细，有两种解决方案：**

**一、使用HashMap：被存进Map后可以直接获取，不用再次计算。**

**二、返回值改成长度为2的数组：**

int[] result = new int[2];

result\[0\]存：节点的一个或两个孩子被偷（图中情况二三）

result\[1\]存：节点被偷（图中情况一）

通过这个result数组保存了两种情况分别偷的金额。

请跳转大佬的链接

[https://leetcode.cn/problems/house-robber-iii/solutions/47828/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/?envType=daily-question&envId=2023-09-18][https_leetcode.cn_problems_house-robber-iii_solutions_47828_san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu_envType_daily-question_envId_2023-09-18]

[https_leetcode.cn_problems_house-robber-iii_description_envType_daily-question_envId_2023-09-18]: https://leetcode.cn/problems/house-robber-iii/description/?envType=daily-question&envId=2023-09-18
[cdfe01f916c94c1593ba81655c0b9f93.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/4874ac34fc064a3ba3767b0805b01b80.png
[6ec4fb80ec584ad7ad3f255103e04027.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/4423d0d204cf4672b7e8ec2b46b855b3.png
[https_leetcode.cn_problems_house-robber-iii_solutions_47828_san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu_envType_daily-question_envId_2023-09-18]: https://leetcode.cn/problems/house-robber-iii/solutions/47828/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/?envType=daily-question&envId=2023-09-18