337. House Robber III (Medium)

https://leetcode.com/problems/house-robber-iii/

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:

Input: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

Output: 7 
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

Solutions

class Solution {

     // Keep the maximum amount of money starting from specific node. You must distinguish following
     // two situations.

     // FIXME

     // if node can be robbed
     Map<TreeNode, Integer> robNodeMaxMoney = new HashMap<>();

     // if node cannot be robbed
     Map<TreeNode, Integer> noRobNodeMaxMoney = new HashMap<>();

     public int rob(TreeNode root) {
          if (root == null) {
               return 0;
          }

          return recurse(root, true);
     }


     private int recurse(TreeNode root, boolean canRob) {
          // return 0 if reach the end
          if (root == null) {
               return 0;
          }

          if (canRob && robNodeMaxMoney.containsKey(root)) {
               return robNodeMaxMoney.get(root);
          }
          if (!canRob && noRobNodeMaxMoney.containsKey(root)) {
               return noRobNodeMaxMoney.get(root);
          }

          // not rob, the max money from left branch
          int max1 = 0;

          // not rob, the max money from right branch
          int max2 = 0;

          // rob, the max money from left branch
          int max3 = 0;

          // rob, the max money from right branch
          int max4 = 0;

          int ans = 0;

          // if parent node robbed, current one cannot be robbed
          if (!canRob) {
               max1 = Math.max(recurse(root.left, true), max1);
               max2 = Math.max(recurse(root.right, true), max2);

               ans = max1 + max2;

               // choose the best robbing scheme for current node
               noRobNodeMaxMoney.put(root, ans);
          }
          // if parent node not robbed, for current one you can choose rob or not.
          else {
               // you can rob but you give up
               max1 = Math.max(recurse(root.left, true), max1);
               max2 = Math.max(recurse(root.right, true), max2);

               // you can rob and you do rob
               max3 = Math.max(recurse(root.left, false), max3);
               max4 = Math.max(recurse(root.right, false), max4);

               // + root.val means rob current node
               ans = Math.max(max1 + max2, max3 + max4 + root.val);

               // choose the best robbing scheme for current node
               robNodeMaxMoney.put(root, ans);
          }

          // return
          return ans;
     }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""