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简洁高效](https://blog.csdn.net/happyaaaaaaaaaaa/article/details/50880121https://blog.csdn.net/happyaaaaaaaaaaa/article/details/50880121)

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

  /**
   * 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 ```Java /**
- 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; } } } ```