题目描述

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

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

示例 1:

输入: [3,2,3,null,3,null,1]
     3 
    / \
    2   3
     \   \ 
      3   1
输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]
      3
     / \
    4   5
   / \   \ 
  1   3   1
 输出: 9
 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/house-robber-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法1 – Top-down

我们以递归的思想来解这道题。对于一个节点node,我们可以选择偷窃也可以选择不偷窃。如果我们选择偷窃,那么node.left与node.right任何一个都不能偷窃了,因为题目说了两个直接相连节点不能同时偷窃。如果我们选择不偷窃node,那么node.left/node.right可以偷窃也可以不偷窃,这与处理node的情况是一致的。

我们定义一个函数“private int withOrWithoutRoot(TreeNode root)”来解决问题,这个函数返回偷窃node或者不偷窃node这两种选择的最大值。我们再定义一个函数“private int withRoot(TreeNode node)”,这个函数解决偷窃node产生的最大值;还有一个函数“private int withoutRoot(TreeNode node)”,它解决不偷窃node产生的最大值。

withRoot函数实现了偷窃node的最大值,那么它应该返回“return node.val + withoutRoot(node.left) + withoutRoot(node.right);”,因为node.left和node.right都不能再偷了,否则node和左右两个子节点就连续了。withoutRoot函数选择不偷窃node的最大值,那么它应该返回“return withOrWithoutRoot(node.left) + withOrWithoutRoot(node.right);”。注意,我们不偷窃node,选择同时偷窃node.left与node.right不一定产生最大收益,如果偷窃了node.left与node.right,我们会丢掉偷窃node.left.left、node.left.right、node.right.left和node.right.right的机会。因此,withoutRoot应该返回“withOrWithoutRoot(node.left) + withOrWithoutRoot(node.right)”。

当整棵树是一条链时,时间复杂度最大为O(n^2),空间复杂度为O(n)。全部代码如下:

class Solution {
    public int rob(TreeNode root) {
        return withOrWithoutRoot(root);
    }

    private int withOrWithoutRoot(TreeNode root) {
        if (root == null)
            return 0;

        return Math.max(withRoot(root), withoutRoot(root));
    }

    private int withRoot(TreeNode node) {
        if (node == null)
            return 0;
        return node.val + withoutRoot(node.left) + withoutRoot(node.right);
    }

    private int withoutRoot(TreeNode node) {
        if (node == null)
            return 0;

        return withOrWithoutRoot(node.left) + withOrWithoutRoot(node.right);
    }
}

解法1 优化

解法1会有重复求解的过程,我们可以利用Map来存储已经计算过的节点。这样,我们只要访问全部节点一次就可以求得答案,时间复杂度为O(n),空间复杂度为O(n)。

全部代码如下:

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map<TreeNode, Integer> cache;

    public int rob(TreeNode root) {
        cache = new HashMap<>();
        return withOrWithoutRoot(root);
    }

    private int withOrWithoutRoot(TreeNode root) {
        if (root == null)
            return 0;

        Integer ans = cache.get(root);

        if (ans == null) {
            ans = Math.max(withRoot(root), withoutRoot(root));
            cache.put(root, ans);
        }

        return ans;
    }

    private int withRoot(TreeNode node) {
        if (node == null)
            return 0;
        return node.val + withoutRoot(node.left) + withoutRoot(node.right);
    }

    private int withoutRoot(TreeNode node) {
        if (node == null)
            return 0;

        return withOrWithoutRoot(node.left) + withOrWithoutRoot(node.right);
    }
}

解法2 – Bottom-up

当然,我们可以自下而上的计算,当访问到叶节点再返回结果。每个节点向parent返回两个结果,一个是取node返回的最大值,另一个是不取node返回的最大值。parent节点再根据叶节点返回的值决定要不要使用自己。自下而上的计算不会发生重复计算的情况,因为已经把已有的所有可能都准备好了,父节点挑选最大的就可以,所以也不需要cache。

时间复杂度O(n),空间复杂度O(n)。全部代码如下:

class Solution {
    public int rob(TreeNode root) {
        // ans[0]表示取node形成的最大值,ans[1]表示不取node形成的最大值
        int[] ans = pickupMax(root);

        return Math.max(ans[0], ans[1]);
    }

    private int[] pickupMax(TreeNode node) {
        if (node == null)
            return new int[2];

        int[] l = pickupMax(node.left);
        int[] r = pickupMax(node.right);
        int[] ans = new int[2];

        ans[0] = node.val + l[1] + r[1]; // 如果我们取node,那么node.left, node.right都不能取
        ans[1] = Math.max(l[0], l[1]) + Math.max(r[0], r[1]); // 如果不取node,那么node.left与node.right可以选择取或者不取

        return ans;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *