337. House Robber III.md

337. House Robber III

Question

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.

Thinking:

• Method 1: 自己的想法是使用bfs + dp，但是[2,1,3,null,4]等例子通过不了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int res1 = 0, res2 = 0;
        if(root == null) return res1;
        LinkedList<TreeNode> q = new LinkedList<>();
        q.offer(root);
        List<Integer> list = new LinkedList<>();
        while(!q.isEmpty()){
            int num = q.size();
            int count = 0;
            for(int i = 0; i < num; i++){
                TreeNode node = q.poll();
                count += node.val;
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
            }
            list.add(count);
        }
        Integer[] nums = new Integer[list.size()];
        Integer[] arr = list.toArray(nums);
        int[] dp = new int[arr.length + 1];
        for(int i = 1; i <= arr.length; i++){
            dp[i] = Math.max(dp[i - 1], arr[i - 1] + (i > 1 ? dp[i - 2]: 0));
        }
        return dp[arr.length];
    }
}

• Method 2： 参考了leetcode 337. House Robber III-动态规划|Java|Python简洁高效

  • 如何求出到当前节点的最大值。
  • 我们需要两个条件，到子结点的最大值，孙结点的最大值 + 当前值。

   /**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
   class Solution {
   	public int rob(TreeNode root) {
   		return dfs(root)[0];
   	}
   	private int[] dfs(TreeNode root){
   		int[] max = {0, 0}; //max[0]: 到当前节点的最大值； max[1]: 到子结点的最大值
   		if(root != null){
   			int[] maxLeft = dfs(root.left);
   			int[] maxRight = dfs(root.right);
   			max[1] = maxLeft[0] + maxRight[0];	//子结点的最大值
   			max[0] = Math.max(maxLeft[1] + maxRight[1] + root.val, max[1]);	//当前的最大值为max(孙结点的最大值 + 当前值, 子结点最大值)。
   		}
   		return max;
   	}
   }

Second Time

• Method 1: DFS + DP

   /**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
   class Solution {
   	public int rob(TreeNode root) {
   		return dfs(root)[0];
   	}
   	private int[] dfs(TreeNode node){
   		if(node == null) return new int[]{0, 0};
   		else{
   			int[] left = dfs(node.left);
   			int[] right = dfs(node.right);
   			int[] result = new int[2];
   			result[1] = left[0] + right[0];
   			result[0] = Math.max(result[1], node.val + left[1] + right[1]);
   			return result;
   		}
   	}
   }