百度搜索不到任何网站,响应式网站制作教程,东莞市建设网站培训,怎么做刷赞网站在上次打劫完一条街道之后和一圈房屋后#xff0c;小偷又发现了一个新的可行窃的地区。这个地区只有一个入口#xff0c;我们称之为“根”。 除了“根”之外#xff0c;每栋房子有且只有一个“父“房子与之相连。一番侦察之后#xff0c;聪明的小偷意识到“这个地方的所有房…在上次打劫完一条街道之后和一圈房屋后小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为“根”。 除了“根”之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫房屋将自动报警。计算在不触动警报的情况下小偷一晚能够盗取的最高金额。示例 1:输入: [3,2,3,null,3,null,1]3/ \2 3\ \ 3 1输出: 7
解释: 小偷一晚能够盗取的最高金额 3 3 1 7.
代码
/*** 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) {if(rootnull) return 0;int[] resdfs(root);return Math.max(res[0],res[1]);}public int[] dfs(TreeNode root) {int[] tempnew int[2];if(rootnull) return temp;int[] ldfs(root.left);//返回子节点偷或者不偷的最优解int[] rdfs(root.right);temp[1]l[0]r[0]root.val;//当前节点被偷了左右节点不能再偷了temp[0]Math.max(l[0],l[1])Math.max(r[0],r[1]);//当前节点没有偷左右节点选择最优的偷法return temp;}
}
