题目描述

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

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

示例 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;
    }
}