装修之家_沈阳定制网带式电加热烘箱_宁波seo外包快速推广_淘宝seo是什么意思啊

一、437. 路径总和 III

• 思路：
  采用前缀和的+回溯
• 代码：

class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:ans = 0cnt = defaultdict(int)cnt[0] = 1def dfs(node: Optional[TreeNode], s: int) -> None:if node is None:returnnonlocal anss += node.valans += cnt[s - targetSum]cnt[s] += 1dfs(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] + xans = 0cnt = defaultdict(int)for p in presum:ans += cnt[p - k]   # 满足p2-k = p1的个数cnt[p] += 1return ans

二、236. 二叉树的最近公共祖先

• 代码：

class Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:if root in (None, p, q):return rootleft = 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 = -infdef dfs(node: Optional[TreeNode]) -> int:if node is None:return 0  # 没有节点，和为 0l_val = dfs(node.left)  # 左子树最大链和r_val = dfs(node.right)  # 右子树最大链和nonlocal ansans = max(ans, l_val + r_val + node.val)  # 两条链拼成路径return max(max(l_val, r_val) + node.val, 0)  # 当前子树最大链和（注意这里和 0 取最大值了）dfs(root)return ans