力扣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