代码随想录算法训练营Day39

力扣213.打家劫舍Ⅱ【medium】
力扣543.二叉树的直径【easy】
力扣124.二叉树种的最大路径和【hard】
力扣337.打家劫舍Ⅲ【medium】

一、力扣213.打家劫舍Ⅱ【medium】

题目链接：力扣213.打家劫舍Ⅱ

视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• 分类讨论，考虑是否偷 nums[0]：
  • 如果偷 nums[0]，那么 nums[1] 和 nums[n−1] 不能偷，问题变成从 nums[2] 到 nums[n−2] 的非环形版本，调用 198 题的代码解决
  • 如果不偷 nums[0]，那么问题变成从 nums[1] 到 nums[n−1] 的非环形版本，同样调用 198 题的代码解决。
  • 这两种方案覆盖了所有情况（毕竟 nums[0] 只有偷与不偷，没有第三种选择），所以取两种方案的最大值，即为答案。
• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

2、代码

class Solution:def rob1(self, nums: List[int]) -> int:f0 = f1 = 0for x in nums:new_f = max(f1, f0 + x)f0 = f1f1 = new_freturn f1# 分类讨论，考虑是否偷 nums[0]：# 如果偷 nums[0]，那么 nums[1] 和 nums[n−1] 不能偷，问题变成从 nums[2] 到 nums[n−2] 的非环形版本，调用 198 题的代码解决# 如果不偷 nums[0]，那么问题变成从 nums[1] 到 nums[n−1] 的非环形版本，同样调用 198 题的代码解决。# 这两种方案覆盖了所有情况（毕竟 nums[0] 只有偷与不偷，没有第三种选择），所以取两种方案的最大值，即为答案。def rob(self, nums: List[int]) -> int:return max(nums[0] + self.rob1(nums[2:-1]), self.rob1(nums[1:]))

---

二、力扣543.二叉树的直径【easy】

题目链接：力扣543.二叉树的直径
题解链接：灵茶山艾府

1、思路

• 

• 所以dfs 帮我们找出每个根节点的最长子链

• 利用 ans 拼接起 左右子链 形成潜在的 最长路径 即 直径

• 时间复杂度：$O(n)$

• 空间复杂度：$O(n)$

2、代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:ans = 0def dfs(node:Optional[TreeNode]) -> int:if node is None:return -1l_len = dfs(node.left) + 1r_len = dfs(node.right) + 1nonlocal ansans = max(ans, l_len + r_len)return max(r_len, l_len)dfs(root)return ans

---

三、力扣124.二叉树种的最大路径和【hard】

题目链接：力扣124.二叉树种的最大路径和
题解链接：灵茶山艾府

1、思路

• 这边可能会碰到负数
• 如果节点和已经是负数了，这个子链舍弃，不要了
• 和53的最大子数组和思想一致
• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

2、代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxPathSum(self, root: Optional[TreeNode]) -> int:ans = -infdef dfs(node:Optional[TreeNode]) -> int:if node is None:return 0l_val = dfs(node.left)r_val =dfs(node.right)nonlocal ans ans = max(ans, l_val + r_val + node.val)#dfs 返回的是链的节点值之和，不是直径的节点值之和。return max(max(r_val, l_val) + node.val, 0) dfs(root)return ans

---

四、力扣337.打家劫舍Ⅲ【medium】

题目链接：力扣337.打家劫舍Ⅲ
题解链接：灵茶山艾府

1、思路

• 这是一个树形dp

• 

• 

• 时间复杂度：$O(n)$

• 空间复杂度：$O(n)$

2、代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def rob(self, root: Optional[TreeNode]) -> int:def dfs(node):if node is None:return 0, 0l_rob, l_not_rob = dfs(node.left)r_rob, r_not_rob = dfs(node.right)rob = l_not_rob + r_not_rob + node.valnot_rob = max(l_not_rob, l_rob) + max(r_not_rob, r_rob)return rob, not_robreturn max(dfs(root))

---