本文共 3020 字，大约阅读时间需要 10 分钟。

先序题目：

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

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

示例 1:

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

     3

输出: 7 

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

     3

输出: 9

1.自己最开始看到上面的例子后，最先想到的就是广度遍历，得到每一层的和，然后再想之前两道打家劫舍的题一样使用动态规划。但是后面仔细想想这样子不对，因为取得不一定是同一层的节点。

2.二叉树的问题大概率是用递归解决的。这道题就根据取不取当前节点来分成两种情况。如果取当前节点，那么当前左右子节点肯定不能取，就继续取当前节点的左右子节点的左右子节点；如果不取当前节点，就取左右子节点。比较这两种情况的最大值。

        最开始的代码：这样做从上往下递归，会产生很多重复计算，因此导致在提交的时候超出时

      间限制。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public int rob(TreeNode root) {        return maxCount(root);    }    public int maxCount(TreeNode node) {        if (node == null) {            return 0;        }        //选取当前节点        int count1 = node.val;        if (node.left != null) {            count1 += maxCount(node.left.left) + maxCount(node.left.right);        }        if (node.right != null) {            count1 += maxCount(node.right.left) + maxCount(node.right.right);        }        //不选取当前节点        int count2 = 0;        count2 += maxCount(node.left) + maxCount(node.right);        return Math.max(count1,count2);    }}

        优化：用一个map来存储每个节点的最大值，就可以避免重复计算了。

class Solution {    Map
   
     map = new HashMap<>();    public int rob(TreeNode root) {        return maxCount(root);    }    public int maxCount(TreeNode node) {        if (node == null) {            return 0;        }        if (map.containsKey(node)) {            return map.get(node);        }        //选取当前节点        int count1 = node.val;        if (node.left != null) {            count1 += maxCount(node.left.left) + maxCount(node.left.right);        }        if (node.right != null) {            count1 += maxCount(node.right.left) + maxCount(node.right.right);        }        //不选取当前节点        int count2 = 0;        count2 += maxCount(node.left) + maxCount(node.right);                map.put(node,Math.max(count1,count2));        return map.get(node);    }}
   

3.题解：

class Solution {    public int rob(TreeNode root) {        //用一个数组来存储每种状态的最大值，0位表示取当前节点，1位表示不取当前节点        int[] rootStatus = dfs(root);        return Math.max(rootStatus[0], rootStatus[1]);    }    public int[] dfs(TreeNode node) {        if (node == null) {            return new int[]{0, 0}; //两种状态下的最大值都为0        }        int[] l = dfs(node.left);//计算左子树的        int[] r = dfs(node.right);//计算右子树的        //如果选择当前节点，那么左右子节点就是不选择的情况        int selected = node.val + l[1] + r[1];        //不选择当前节点，根据左右子节点来判断        int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);        return new int[]{selected, notSelected};    }}

题源：

转载地址：https://blog.csdn.net/xxyneymar/article/details/122056400 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！