当前位置: 首页 > article >正文

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

相关文章:

  • 实验5 逻辑回归
  • 梯度下降法以及随机梯度下降法
  • 作业9 (2023-05-05 数组的定义和初始化)
  • 富文本编辑器(Rich Text Editor,RTE)
  • 矩阵交换行(信息学奥赛一本通-1119)
  • 基于NXP+FPGA永磁同步电机牵引控制单元(单板结构/机箱结构)
  • CMU15445(2023fall) Project #2 - Extendible Hash Index 匠心分析
  • 【搭建环境】windows环境redis\集群;rabbitmq
  • 在 Spring Boot 中实现基于 TraceId 的日志链路追踪
  • 编程自学指南:java程序设计开发,Java I/O流,为什么需要I/O流?,Java I/O体系结构,字节流,字符流,对象流与序列化
  • MATLAB 控制系统设计与仿真 - 25
  • 突破连接边界!O9201PM Wi-Fi 6 + 蓝牙 5.4 模块重新定义笔记本无线体验
  • 宇树与智元的崛起:机器人“灵魂”注入的技术密码
  • 电脑热点无法打开
  • 深度求索:DeepSeek的AI技术革新与行业突破
  • nerfstudio以及相关使用记录(长期更新)
  • Redis 源码分析-内部数据结构 quicklist
  • 【存储中间件】Redis核心技术与实战(一):Redis入门与应用(高级数据结构:Bitmaps、HyperLogLog、GEO)
  • Java Spring Boot 常用技术及核心注解
  • 无缝+安全:基于 Power BI Embedded 的外部用户数据共享全解析