导购分享网站模板,宁波公司注册流程,第一ppt免费模板网,玉溪住房和城乡建设局网站题意理解#xff1a; 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口#xff0c;我们称之为 root 。 除了 root 之外#xff0c;每栋房子有且只有一个“父“房子与之相连。一番侦察之后#xff0c;聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”… 题意理解 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为 root 。 除了 root 之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 房屋将自动报警。 给定二叉树的 root 。返回 在不触动警报的情况下 小偷能够盗取的最高金额 。 这里的打家劫舍不同之处在于状态转移是在一颗树上 限制要求是相邻不能偷 所以 偷了根节点左右孩子节点不能偷 偷了左右孩子根节点不能偷 解题思路 这里使用回溯法来遍历每个节点 每个节点都有两种状态偷当前节点和不偷当前节点 所以我们在每层设置一个dp数组 dp[0]表示不偷所能获得的最大金额 dp[1]表示偷所能获得的最大金额。 所以每层返回一个dp数组。 dp[0]max(偷左不偷左 max(偷右不偷右) dp[1]不偷左不偷右根 最后的结果是 max(dp[0],dp[1]) 1.解题 public int rob(TreeNode root) {int[] dpnew int[2];dptravel(root);return Math.max(dp[0],dp[1]);}public int[] travel(TreeNode root){int[] dpnew int[2];if(rootnull) return dp;int[] left_dptravel(root.left);int[] right_dptravel(root.right);dp[0]Math.max(left_dp[0],left_dp[1])Math.max(right_dp[0],right_dp[1]);dp[1]left_dp[0]right_dp[0]root.val;return dp;}
2.分析 时间复杂度O(n) 空间复杂度O(n)
