337.md

337. 打家劫舍 III

题目描述

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

解法一：动态规划+递归

• 若偷当前节点，那么总钱数为 以四个孙子几点为根能偷到的最大钱数之和。
• 若不偷当前节点，那么总钱数为以两个儿子节点为根能偷到的最大钱数之和。

class Solution {
    public int rob(TreeNode root) {
       return helper(root);
    }

    public int  helper(TreeNode node ){
        if(node == null) return 0;
        int money1=0,money2=0;
        //只偷子节点
        money1=helper(node.left)+helper(node.right);
        if(node.left != null){
            //偷子节点的子节点和父节点
            money2+=helper(node.left.left)+helper(node.left.right);
        }
        if(node.right != null){
            //偷子节点的子节点和父节点
            money2+=helper(node.right.left)+helper(node.right.right);
        }
        //获取最大值
        return Math.max(node.val+money2,money1);
    }
}

解法二：在解法一的基础上，改进算法

1. 创建HelpNode，保存了每次搜索的结果，保证了子问题只被计算一次。
2. 算法步骤
   • 构造一个由HelpNode为节点的和原始树结构相同的树。
   • 在新树中进行递归计算如果以当前节点为根则可以偷多少钱，并保存结果防止重复计算。

class Solution {
    public int rob(TreeNode root) {
       if(root == null) return 0;
       HelpeNode newRoot = new HelpeNode(root);
       copyTree(root,newRoot);
       return helper(newRoot);
    }

    public int  helper(HelpeNode node ){
        if(node == null) return 0;
        //判断该节点是否计算过
        if(node.flag) return node.robCount;
        if(node.left == null || node.right == null){
            node.robCount = node.innerNode.val;
            node.flag = true;
        }
        int money1=0,money2=0;
        money1=helper(node.left)+helper(node.right);
        if(node.left != null){
            money2+=helper(node.left.left)+helper(node.left.right);
        }
        if(node.right != null){
            money2+=helper(node.right.left)+helper(node.right.right);
        }
        node.robCount =  Math.max(node.innerNode.val+money2,money1);
        node.flag = true;
        return node.robCount;
    }

    /**
    * 复制数据操作
    */
    public void copyTree(TreeNode root1,HelpeNode root2){
        if (root1.left != null) {
            HelpeNode newNode = new HelpeNode(root1.left);
            root2.left = newNode;
            copyTree(root1.left,root2.left);
        }
        if (root1.right != null){
            HelpeNode newNode = new HelpeNode(root1.right);
            root2.right = newNode;
            copyTree(root1.right,root2.right);
        }
    }

    public static class HelpeNode{
        public TreeNode innerNode;
        public HelpeNode left;
        public HelpeNode right;
        public boolean flag = false;
        public int robCount=0;

        public HelpeNode(TreeNode node){
            this.innerNode=node;
        }
    }
}

解法三：

对于每个节点，用一个数组，int[0]表是不偷当前节点，int[1]表示偷当前节点。

每个节点可选择偷或者不偷两种状态，根据题目意思，相连节点不能一起偷

• 当前节点选择偷时，那么两个孩子节点就不能选择偷了
• 当前节点选择不偷时，两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)

总结：这样做的好处是，一个节点只与和它相邻的节点的信息有关，就不会造成解法一那样的同一子问题求解两遍的问题了。

 public int rob(TreeNode root) {
        int[] rob = robHelper(root);
        return Math.max(rob[0],rob[1]);
    }

    public int[] robHelper(TreeNode root){
        //0 存储不偷，1 存储偷
        int[] rop = new int[2];
        if(root == null) return rop;

        int[] left = robHelper(root.left);
        int[] right = robHelper(root.right);

        //不偷当前节点，则直接获取子节点的最大值
        rop[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        //偷当先节点，则不偷子节点
        rop[1] = root.val+left[0]+right[0] ;

        return rop;
    }