leetcode打家劫舍3
2022/3/20 23:29:19
本文主要是介绍leetcode打家劫舍3,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
- 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。
- 除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。
- 给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。
链接:https://leetcode-cn.com/problems/house-robber-iii
使用二叉树递归套路
分析:该题通过考虑偷不偷根节点来考虑
- 第一种情况 :
偷根节点 : 收益 = root.val + 在不偷左子树的最大收益 + 在不偷右子树的最大收益 - 第二种情况:
注意: 在不偷根节点时,左右子树可以偷也可以不偷
不偷根节点 : 收益 = 0 + max(偷左子树的最大收益, 不偷左子树的最大收益) + max(偷右子树的最大收益 , 不偷右子树的最大收益) - ==> 返回值类型为 :
偷当前节点的最大收益(stealMax), 不偷当前节点的最大收益(notStealMax
/** * 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 { class ReturnType{ int stealMax; int notStealMax; public ReturnType() { } public ReturnType(int stealMax, int notStealMax) { this.stealMax = stealMax; this.notStealMax = notStealMax; } } public int rob(TreeNode root) { if (root == null) { return 0; } // 只有一个节点时只能偷了 if (root.left == null && root.right == null) { return root.val; } ReturnType result = process(root); return Math.max(result.notStealMax, result.stealMax); } private ReturnType process(TreeNode root) { if (root == null) { return new ReturnType(0,0); } ReturnType leftReturn = process(root.left); ReturnType rightReturn = process(root.right); // 偷root int stealRoot = root.val + leftReturn.notStealMax + rightReturn.notStealMax; // 不偷root int notStealRoot = Math.max(leftReturn.notStealMax, leftReturn.stealMax) + Math.max(rightReturn.notStealMax, rightReturn.stealMax); return new ReturnType(stealRoot,notStealRoot); } }
这篇关于leetcode打家劫舍3的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享