题目

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

  1. Input: [3,2,3,null,3,null,1]
  3.      3
  4.     / \
  5.    2   3
  6.     \   \ 
  7.      3   1
  9. Output: 7 
  10. Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

  1. Input: [3,4,5,1,3,null,1]
  3.      3
  4.     / \
  5.    4   5
  6.   / \   \ 
  7.  1   3   1
  9. Output: 9
  10. Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

题意

给定一个二叉树，从中选取互不直接相连的若干数，使其和最大。

思路

直接暴力递归也能过，为了优化加上记忆化。

代码实现

Java

  1. class Solution {
  2.     public int rob(TreeNode root) {
  3.         Map<TreeNode, Integer> memTo = new HashMap<>();
  4.         Map<TreeNode, Integer> memNot = new HashMap<>();
  5.         return Math.max(rob(root, true, memTo, memNot), rob(root, false, memTo, memNot));
  6.     }
  8.     private int rob(TreeNode root, boolean canRob, Map<TreeNode, Integer> memTo, Map<TreeNode, Integer> memNot) {
  9.         if (root == null) {
  10.             return 0;
  11.         }
  13.         if (canRob && memTo.containsKey(root)) {
  14.             return memTo.get(root);
  15.         }
  17.         if (!canRob && memNot.containsKey(root)) {
  18.             return memNot.get(root);
  19.         }
  21.         int toRob = canRob ? root.val + rob(root.left, false, memTo, memNot) + rob(root.right, false, memTo, memNot) : 0;
  22.         int notRob = rob(root.left, true, memTo, memNot) + rob(root.right, true, memTo, memNot);
  23.         int tmp = Math.max(toRob, notRob);
  25.         if (canRob) {
  26.             memTo.put(root, tmp);
  27.         } else {
  28.             memNot.put(root, tmp);
  29.         }
  31.         return tmp;
  32.     }
  33. }