题目

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

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

示例 1:

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

  1.  3<br />    / \<br />   2   3<br />    \   \ <br />     3   1

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

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

 3<br />    / \<br />   4   5<br />  / \   \ <br /> 1   3   1

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的思路

1.找出不相连的树结点的最大集合 比如示例1中的集合为{3,3,1}，{2,3}。 示例2中的集合为{3,1,3,1}，{4,5}
2.什么样的树不相连？ 结点高度差大于1的 或者是兄弟结点 也就是 计算奇数层相加 和偶数层相加 哪个比较大
3.所以，我们可以借助队列，将根结点入队，然后弹出根结点，加入奇数层计数集合中，同时将根结点下一层入队，
然后弹出，加入偶数层计数集合中，以此循环，知道队列为空。

我的代码

class Solution {
    public int rob(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //java队列的增加和删除为queue.offer和queue.poll
        TreeNode Bin;
        int result1=0;
        int result2=0; //奇数层计数器和偶数层计数器
        int count=2;
        queue.offer(root);
        while(!queue.isEmpty())
        {
            Bin=queue.poll();
            if(count%2==0)
            {
                result1+=Bin.val;
                count++;
            }
            else
            {
                result2+=Bin.val;
                count++;
            }
            if(root.left!=null)  queue.offer(root.left);
            if(root.right!=null)  queue.offer(root.right);
        }
        if(result1>result2)
        {
            return result1;
        }
        else
        {
            return result2;
        }
    }

哈哈哈,经过测试,这是个愚蠢无比的代码.
首先,隔行求和并不对,因为1个儿子和另外的两个孙子之间也可以求和,或者说一个爷爷和它的曾孙子,所以算法的正确性就有很大的问题,更不要说执行起来还很慢.

leetcode官方题解

简化一下这个问题：一棵二叉树，树上的每个点都有对应的权值，每个点有两种状态（选中和不选中），问在不能同时选中有父子关系的点的情况下，能选中的点的最大权值和是多少。

我们可以用 f(o) 表示选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和；g(o) 表示不选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和；l 和 r 代表 o 的左右孩子。

当 o 被选中时，o 的左右孩子都不能被选中，故 o 被选中情况下子树上被选中点的最大权值和为 l 和 r 不被选中的最大权值和相加，即 f(o) =g(l)+g(r)。
当 o 不被选中时，o 的左右孩子可以被选中，也可以不被选中。对于 o 的某个具体的孩子 x，它对 o 的贡献是 x 被选中和不被选中情况下权值和的较大值。故 g(o) = \max { f(l) , g(l)}+\max{ f(r) , g(r) }g(o)=max{f(l),g(l)}+max{f(r),g(r)}。
至此，我们可以用哈希映射来存 f 和 g 的函数值，用深度优先搜索的办法后序遍历这棵二叉树，我们就可以得到每一个节点的 f 和 g。根节点的 f 和 g 的最大值就是我们要找的答案。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/house-robber-iii/solution/da-jia-jie-she-iii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

java代码

class Solution {
    Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
    Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();

    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
    }

    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        dfs(node.right);
        f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
        g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
    }
}

总结思考

第一次刷算法题,感觉有点像高中时候解数学题,审题要仔细,把题目的意思理解清楚,抽象出对应的数学公式,根据公式来写代码.没有过不要泄气,嘻嘻,相信自己迟早能考150.