337. House Robber III

Link

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.

Solution

Way 1, recursion 關於optimized的問題，會傾向讓子問題也optimized，那麼最後的optimize就是各個子問題的optimzed的和。

接下來就是考慮下列兩個重要問題 Q1. 不需要任何計算的最小問題的答案 (base case) Q2. 如何把問題變小以及最後如何組成最後答案 A1: 通常是在元素null或是只有一個的時候。 以這題為例。最小的case是 root == null,此時應該是0 A2: 因為tree的特性，可以切成左子樹跟右子樹，把問題縮減的方向應該也是將他們縮減成左右子樹所構成的子問題。

接下來觀察題目的限制，發現不能接受兩個node同時被rob (ie. It will automatically contact the police if two directly-linked houses were broken into on the same night.)。

所以當node被rob之後，問題會縮減成 rob(node.left.left) rob(node.left.right) rob(node.right.left) rob(node.right.right) 等由grandChild所構成的子問題組合 int robRoot = root.val + rob(node.left.left) + rob(node.left.right) + rob(node.right.left) + rob(node.right.right);

反之當node沒被rob時則無任何限制 為rob(node.left) + rob(node.right)的組合 int notRobRoot = rob(root.left) + rob(root.right);

最後node取與不取只能有一個存在。所以取這兩種可能的最大值 return Math.max(robRoot , notRotRoot);

T: O(4^N) , 每個node都會衍伸出4次function

 public int rob(TreeNode root) {
     
        if(root == null) return 0;
         
        int robRoot = root.val;
        
        if(root.left != null){
            robRoot += rob(root.left.left) + rob(root.left.right); 
        }
        if(root.right != null){
            robRoot += rob(root.right.left) + rob(root.right.right); 
        }
        
        int notRobRoot = rob(root.left) + rob(root.right);
        
        return Math.max(robRoot, notRobRoot);
    }

Way 2: DP

目前觀察DP通常就是解決recursion時間複雜度太高的問題(通常是expornation)，會這麼高的原因是因為很多子問題被重複計算了。

比較直觀的方法就是建立一個global的資料結構(ex. array, hashMap)等去計算子問題的答案，當子問題被query時，可以直接回傳之前的答案。 T: O(N)

 HashMap<TreeNode, Integer> map = new HashMap<>();
    public int rob(TreeNode root) {
        if(root == null) return 0;
        if(map.containsKey(root)){
            return map.get(root);
        } 
        
        int robRoot = root.val;
        
        if(root.left != null){
            robRoot += rob(root.left.left) + rob(root.left.right); 
        }
        if(root.right != null){
            robRoot += rob(root.right.left) + rob(root.right.right); 
        }
        
        int notRobRoot = rob(root.left) + rob(root.right);
        int ret = Math.max(robRoot, notRobRoot);
        map.put(root, ret);
        return ret;
    }

Way 3. DP without hashMap

這部分我覺得有點tricky，不琢磨太多時間。基本上就是把ret變成int[2]，分成有robNode跟沒robNode。 這樣計算的時候就有點類似button up。不會重複計算子問題。

   public int rob(TreeNode root) {
        int[] ret = rob2(root);
        return Math.max(ret[0], ret[1]);
    }
    
    public int[] rob2(TreeNode node){
        
        if(node == null) return new int[]{0,0};
        int[] ret = new int[2];
        int[] L = rob2(node.left);
        int[] R = rob2(node.right);
        
        ret[0] = node.val + L[1] + R[1];
        ret[1] = Math.max(L[0], L[1]) + Math.max(R[0], R[1]);
        return ret;
    }