337. House Robber III——树的题目几乎都是BFS、DFS,要么递归要么循环
2023-09-14 09:11:57 时间
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "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 forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
3 / \ 2 3 \ \ 3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3 / \ 4 5 / \ \ 1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def rob(self, root): """ :type root: TreeNode :rtype: int 3 => 3 3 => 3 / 2 3 \ 3 =>3=max(3,3) 3 / \ => 3+2=5=max(3, 2+3) 2 3 3 / \ 2 3 \ 3 => 3+3=6=max(3+3,2+3)=max(3+node2,3 not choose, node2,3 choosed) 1 / \ 4 1 / \ \ 1 1 5 => 4+5=9=max(3+3+1+1,4+5)=9 """ return max(self.rob_helper(root)) def rob_helper(self, root): if root is None: return [0, 0] ans = [0]*2 ans_left = self.rob_helper(root.left) ans_right = self.rob_helper(root.right) ans[0] = max(ans_left[0], ans_left[1]) + max(ans_right[0], ans_right[1]) ans[1] = ans_left[0] + ans_right[0] + root.val return ans
相关文章
- python跳出循环重新开始_python怎么跳出循环
- 循环神经网络初探
- shell中的while循环实例[通俗易懂]
- 递归改成循环_递归比循环效率高吗
- less循环生成n个类
- 使用1.8新特性stream+lambda实现递归无限极循环
- SQL递归实现循环判断
- 数据结构【Golang实现】(四)——双向循环链表
- Sql存储过程游标循环的用法及sql如何使用cursor写一个简单的循环
- 如何在多层循环中跳出循环呢详解编程语言
- 利用Oracle循环删除多张表数据(oracle循环删表)
- 实现Redis存储能力从循环取值开始(循环从redis取值)
- 用PHP实现递归循环每一个目录
- 友情链接横向文字上下间隙循环滚动JS效果
- 循环vs递归浅谈
- C#条件语句、循环语句(if、while)