力扣（LeetCode)每日一题 337. 打家劫舍 III-蒲公英云

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

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

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

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

再细分为两种情况：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);
    }
}

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

超时的原因：根节点的孙子被重复计算了，（三辈份：爷爷父亲孙子 —— 爷爷需要计算一次父亲计算一次孙子，父亲计算一次孙子，孙子辈被计算了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