[leetcode]337. House Robber III

分手后的思念是犯贱 2022-08-22 00:01 149阅读 0赞

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:

3
        / \
       2   3
        \   \ 
         3   1

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

Example 2:

3
        / \
       4   5
      / \   \ 
     1   3   1

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

**算法分析**：

依然是这个场景，只不过“所有的房屋形成了一个二叉树结构”。首先我们可以明确的是，对于一棵给定的二叉树，每个结点可以对应一棵子树，而每棵子树的最大可偷盗金额（暂且称之为rob值）是确定的，我们需要求的是根结点的rob值。我依然尝试用递归的思想：可不可以先计算出根结点的左儿子和右儿子的rob值，然后得到根结点的rob值？答案是肯定的。不过，我们只从左右儿子的rob值和结点本身的val值还不足以推出该结点的rob值。因为倘若

1）左儿子和右儿子取得最大rob值时，左儿子和右儿子都没有被选中，则该结点的rob值可以等于左右儿子的rob值和结点本身的val值之和；

2）左儿子和右儿子取得最大rob值时，左儿子和右儿子都被选中，情况就变得很复杂。

进一步思考，我们可以记录下每个结点的include值和exclude值，其中，include值是包括该结点在内的最大可偷盗金额，exclude值是不包括该结点的最大可偷盗金额。每个结点的include值和exclude值完全可以通过其左右儿子的include值和exclude值得到。推导规则如下：

root.include = root.val + left.exclude + right.exclude

root.exclude = max(left.include,left.exclude) + max(right.include,right.exclude)

其中，root表示原结点，left表示其左儿子，right表示其右儿子。max是取两个数较大的那个。

**数据结构分析**：

由于题目帮我们建好的类中没有exclude和include两个属性，于是我们自己新建一个类将这两个属性加进去。然后遍历二叉树的同时把我们需要的树（带有exclude和include属性值的数）建好。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public class MyNode {
            int val;
            int exclude;
            int include;
            MyNode left;
            MyNode right;
        }
        
        
        public int rob(TreeNode root) {
            if(root == null){
                return 0;
            }
            MyNode my = genMyNode(root);
            calRob(my);
            return my.exclude > my.include ? my.exclude : my.include;
        }
        
        /**
         * 生成带有include和exclude属性的二叉树
         */
        private MyNode genMyNode(TreeNode root){
            MyNode my = new MyNode();
            my.val = root.val;
            if(root.left != null){
                my.left = genMyNode(root.left);
            }
            else{
                my.left = null;
            }
            if(root.right != null){
                my.right = genMyNode(root.right);
            }
            else{
                my.right = null;
            }
            return my;
        }
        
        /**
         * 计算include值和exclude值
         */
        private void calRob(MyNode root){
            if(root.left == null && root.right == null){
                root.include = root.val;
                root.exclude = 0;
            }
            else if(root.left == null && root.right != null){
                calRob(root.right);
                root.include = root.val + root.right.exclude;
                root.exclude = root.right.exclude > root.right.include ? root.right.exclude : root.right.include;
            }
            else if(root.left != null && root.right == null){
                calRob(root.left);
                root.include = root.val + root.left.exclude;
                root.exclude = root.left.exclude > root.left.include ? root.left.exclude : root.left.include;
            }
            else{
                calRob(root.left);
                calRob(root.right);
                root.include = root.val + root.left.exclude + root.right.exclude;
                root.exclude = (root.left.exclude > root.left.include ? root.left.exclude : root.left.include) + (root.right.exclude > root.right.include ? root.right.exclude : root.right.include);
            }
            
        }
    }