二叉树(Binary|LeetCode 337. House Robber III - 二叉树系列题25
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root
.
Besides the root
, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Given the root
of the binary tree, return the maximum amount of money the thief can rob without alerting the police.
Example 1:
文章图片
Input: root = [3,2,3,null,3,null,1] Output: 7 Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
文章图片
Input: root = [3,4,5,1,3,null,1] Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]
. 0 <= Node.val <= 104
问题的关键是不能连续偷两个房子,如果是从上往下偷,那么偷了当前节点就不能偷它的两个子节点;如果是从下往上偷,那么偷了当前节点就不能偷它的父节点。根据二叉树的特性,从下往上最终汇聚于根节点,最后只要判断根节点的状态,因此从下往上更方便于计算。对于一个节点有两种状态,被偷或者没被偷,它的状态取决于其左右子节点的状态:
1)当前节点被偷:它的两个子节点都没被偷
2)当前节点没被偷:不能偷如果它的两个子节点至少有一个被偷,或者小偷不想偷。
因此,从下往上传递两个值,到当前节点为止以当前节点为根节点的子树中,当前节点被偷,小偷得到的最多钱为两个子节点都没没被偷得到的最多钱加上当前节点的钱。当前节点没被偷,小偷能得到的最多钱为两个子节点所有状态中最多钱的和。
最后汇总到了根节点,根节点被偷或没被偷中的更大者就是答案。
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def helper(node):
if not node:
return [0, 0]
left = helper(node.left)
right = helper(node.right)
rob = node.val + left[1] + right[1]
notRob = max(left) + max(right)
return [rob, notRob]res = helper(root)
return max(res[0], res[1])
【二叉树(Binary|LeetCode 337. House Robber III - 二叉树系列题25】
推荐阅读
- 算法训练(C语言版本)|112. 路径总和
- 小项目集合|C语言小项目——通讯录(适合刚学完C语言的初学者)
- Python中转换数据类型的函数
- Python中常用数据类型转换函数的使用方法和步骤
- Pycharm交互式开发环境的使用方法
- LeetCode|【每日一题】——合并区间
- LeetCode|【每日一题】——单调递增的数字
- python|python批量修改txt文件里的类别数,批量修改文件名
- 深度学习|yolov5-v6.1发布