力扣hot100_二叉树(5)_python版本
一、437. 路径总和 III
- 思路:
采用前缀和的+回溯 - 代码:
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
ans = 0
cnt = defaultdict(int)
cnt[0] = 1
def dfs(node: Optional[TreeNode], s: int) -> None:
if node is None:
return
nonlocal ans
s += node.val
ans += cnt[s - targetSum]
cnt[s] += 1
dfs(node.left, s)
dfs(node.right, s)
cnt[s] -= 1 # 恢复现场
dfs(root, 0)
return ans
1.1 类似题目:560. 和为 K 的子数组
- 思路:
首先,和为k的子数组这种题,只能使用前缀和,无法使用滑动窗口(滑动窗口需要满足单调性,当右端点元素进入窗口时,窗口元素和是不能减少的)。
第二,要找到和为k的子数组,其实就是找到presum[j] - presum[i] = k,变形一下,presum[i] = presum[j] - k,相当于遍历整个presum数组,找到满足上式的个数。 - 代码:
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
presum = [0] * (len(nums) + 1)
for i, x in enumerate(nums):
presum[i + 1] = presum[i] + x
ans = 0
cnt = defaultdict(int)
for p in presum:
ans += cnt[p - k] # 满足p2-k = p1的个数
cnt[p] += 1
return ans
二、236. 二叉树的最近公共祖先
- 代码:
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if root in (None, p, q):
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right: # 左右都找到
return root # 当前节点是最近公共祖先
return left or right
三、124. 二叉树中的最大路径和
- 代码:
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
ans = -inf
def dfs(node: Optional[TreeNode]) -> int:
if node is None:
return 0 # 没有节点,和为 0
l_val = dfs(node.left) # 左子树最大链和
r_val = dfs(node.right) # 右子树最大链和
nonlocal ans
ans = max(ans, l_val + r_val + node.val) # 两条链拼成路径
return max(max(l_val, r_val) + node.val, 0) # 当前子树最大链和(注意这里和 0 取最大值了)
dfs(root)
return ans
原文地址:https://blog.csdn.net/yin2567588841/article/details/146187099
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/585608.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/585608.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!