124 二叉树中的最大路径和

又是一个hard题目,其实我大概有想到要去dfs遍历节点,当时不知道怎么从一个叶子结点开始遍历。其实只需要从根节点出发,看看左右节点加在一起是否最大能不能作为一个路径,但是对外这是要不左节点上来要不右节点上来,不能两个结点都上来要不然会重复

题目

二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ,返回其 最大路径和

示例 1:

输入: root = [1,2,3]
输出: 6
解释: 最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6

代码与解析

代码上有注释,详细的思路解答

class Solution {
    int maxSum = Integer.MIN_VALUE; // 用于记录最大路径和

    /**
     * 计算二叉树中任意节点的最大路径和
     * @param root 给定的二叉树根节点
     * @return 返回最大路径和
     */
    public int maxPathSum(TreeNode root) {
        // 如果树只有一个节点,则直接返回该节点的值
        if(root.left == null && root.right == null) return root.val;

        // 调用深度优先搜索方法
        dfs(root);

        return maxSum;
    }

    /**
     * 深度优先搜索计算路径和
     * @param node 当前节点
     * @return 返回当前节点向下路径和的最大值
     */
    public int dfs(TreeNode node) {
        if(node == null) return 0; // 空节点返回0

        int l = Math.max(dfs(node.left), 0); // 左子树提供的最大路径和,负值设为0
        int r = Math.max(dfs(node.right), 0); // 右子树提供的最大路径和,负值设为0

        int innerMax = l + r + node.val; // 当前子树内部的最大路径和
        maxSum = Math.max(maxSum, innerMax); // 更新最大路径和

        int outSum = node.val + Math.max(0, Math.max(l, r)); // 当前节点向上提供的最大路径和
        return outSum < 0 ? 0 : outSum; // 若对外提供的路径和为负,返回0;否则返回路径和
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/296591.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

LeetCode(40)组合总和Ⅱ⭐⭐

给定一个候选人编号的集合 candidates 和一个目标数 target &#xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意&#xff1a;解集不能包含重复的组合。 示例 1: 输入: candidates [10,1,2,7,6,…

热图分析(这个热力图代表的是不同描述符与pIC50之间的皮尔逊相关系数。)

案例一&#xff1a; 这个热力图代表的是不同描述符与pIC50之间的皮尔逊相关系数。pIC50是一种表示化合物在生物学测定中抑制效果的负对数IC50值&#xff0c;它通常用于药物发现和评估中&#xff0c;用来量化化合物对特定靶标的抑制能力。 要分析这个热力图&#xff0c;你需要关…

vue3-admin-element框架实现动态路由(根据接口返回)

第一步&#xff1a;在src-utils-handleRoutes&#xff0c;修改代码&#xff1a; export function convertRouter(routers) {let array [];for (let i in routers) {for (let s in asyncRoutes) {if (routers[i].path asyncRoutes[s].path) {array.push({ ...asyncRoutes[s] …

CNN——GoogLeNet

1.GoogLeNet简介 GoogLeNet是谷歌推出的基于Inception模块深度卷积神经网络结构。L和N大写还是为了致敬LeNet。在随后的两年中一直在改进&#xff0c;形成了Inception V2、Inception V3、Inception V4等版本。GoogLeNet&#xff08;Inception-V1&#xff09;&#xff0c;在Imag…

鸿蒙学习笔记

DevEco Studio, ArkTS, ArkUI, ArkCompiler, DevEco Testing是啥 DevEco Studio是华为开发的一款集成开发环境&#xff08;IDE&#xff09;&#xff0c;用于开发基于华为鸿蒙操作系统&#xff08;HarmonyOS&#xff09;的应用程序。它提供了丰富的开发工具和功能&#xff0c;包…

武汉灰京文化:技术先锋辐射游戏行业,带来全新体验乐趣无穷!

科技的持续演进&#xff0c;给游戏产业打了强心剂&#xff0c;让这个领域变得前所未有的越来越好玩儿。今天我们将深入探讨如何利用虚拟现实&#xff08;VR&#xff09;和增强现实&#xff08;AR&#xff09;技术&#xff0c;让你玩得开心&#xff0c;玩得尽兴。 想象一下&…

在pycharm中jupyter连接上了以后显示无此库,但是确实已经安装好了某个库,使用python可以跑,但是使用ipython就跑不了

今天遇到一个事情&#xff0c;就是用pycharm的jupyter时&#xff0c;连接不上&#xff0c;后来手动连接上了以后&#xff0c;发现环境好像不对。 一般来说&#xff0c;这里会是python3&#xff0c;所以里面的环境也是普通python的环境&#xff0c;并没有我下载的库&#xff0c;…

计算机毕业设计-----SSM餐厅点餐收银管理系统

项目介绍 用于餐厅的收银管理系统&#xff0c;包含了四个模块 1.桌位模块 桌位模块主要是用于管理桌位的模块&#xff0c;包括点菜到结账的流程 将桌位人数设置为0可以滞空当前桌位 2.账单模块 账单模块记录了每一天的帐单汇总&#xff0c;同时提供了年月日账单的统计&#x…

mysql之CRUD和常见函数和UNION 和 UNION ALL

mysql之CRUD和常见函数和UNION 和 UNION ALL 一.CRUD1.创建&#xff08;Create&#xff09; - 插入数据2.读取&#xff08;Read&#xff09; - 查询数据3.更新&#xff08;Update&#xff09; - 修改数据4.删除&#xff08;Delete&#xff09; - 删除数据 二.函数1.字符串函数&…

二刷Laravel 教程(构建页面)总结Ⅰ

L01 Laravel 教程 - Web 开发实战入门 ( Laravel 9.x ) 一、功能 1.会话控制&#xff08;登录、退出、记住我&#xff09; 2.用户功能&#xff08;注册、用户激活、密码重设、邮件发送、个人中心、用户列表、用户删除&#xff09; 3.静态页面&#xff08;首页、关于、帮助&am…

五、Spring AOP面向切面编程(基于XML方式实现)

本章概要 Spring AOP基于XML方式实现(了解)Spring AOP对获取Bean的影响理解 根据类型装配 bean使用总结 5.6 Spring AOP基于XML方式实现(了解) 准备工作 加入依赖 <!-- spring-aspects会帮我们传递过来aspectjweaver --> <dependency><groupId>org.spr…

Langchain模板-LangChainTemplates 讲解及应用

langchain官方链接&#xff1a;https://github.com/langchain-ai/langchain/tree/master/templates 其他相关链接&#xff1a; https://python.langchain.com/docs/templates https://templates.langchain.com/ Langchain模板&#xff0c;提供一系列的易于部署的参考架构&a…

基于 Python+Django 技术栈,我开发了一款视频管理系统

学习过程中&#xff0c;遇到问题可以咨询作者 大家好&#xff0c;作为一名开发人员&#xff0c;平时比较愿意动手尝试各种有意思工具&#xff0c;因为笔者非常喜欢观看视频&#xff0c;尤其是YouTube、bilibili都是笔者非常喜欢的视频网站&#xff0c;所以想自己实现一个视频点…

Java/JDK下载安装与环境配置

Java由Sun Microsystems&#xff08;现在是Oracle的子公司&#xff09;于1995年首次发布。它是一种面向对象的编程语言&#xff0c;广泛应用于Web开发、移动应用程序开发、桌面应用程序开发和企业级应用程序开发等领域。 Java语言的主要特点是跨平台、可移植性强、安全性高和具…

代码随想录-刷题第四十八天

198. 打家劫舍 题目链接&#xff1a;198. 打家劫舍 思路&#xff1a;当前房屋偷与不偷取决于前一个房屋和前两个房屋是否被偷了。这里就更感觉到&#xff0c;当前状态和前面状态会有一种依赖关系&#xff0c;那么这种依赖关系都是动规的递推公式。动态规划五步曲&#xff1a;…

C#编程-实现继承

C#允许您通过扩展现有类的功能以创建新类来实现继承。 从基类创建派生类 使用以下语法在C#中创建派生类: class <derived_class>:<base_class>{...}确定继承的层次结构 要确定继承层次结构,必须检查派生类与基类之间的关系种类。确保派生类是一种基类。 请考虑以…

【深度学习】SDXL tensorRT 推理

stabilityai/stable-diffusion-xl-1.0-tensorrt 项目&#xff1a;https://huggingface.co/stabilityai/stable-diffusion-xl-1.0-tensorrt TensorRT环境&#xff1a; git clone https://github.com/rajeevsrao/TensorRT.git cd TensorRT git checkout release/9.2stabilitya…

数据结构—图(上)

文章目录 12.图(上)(1).图的基本概念#1.图的基本定义#2.边的分类#3.数据结构的一些规定#4.子图#5.完全图#6.路径#7.连通性和连通分量#8.度 (2).图的存储方式#1.邻接矩阵#2.邻接表 (3).图的遍历#1.深度优先搜索(Depth First Search)i.走个迷宫ii.DFS的思想iii.代码实现 #2.广度优…

基于SSM的图书商城(有报告)。Javaee项目。ssm项目。

演示视频&#xff1a; 基于SSM的图书商城&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c;通过Spring SpringMv…

word2019保存后的图片变模糊了怎么办?Word 2019 默认保存后压缩变模糊的问题,解决方案

Word 2019 默认保存后压缩变模糊的问题&#xff0c;解决方案 1&#xff0c;新建word 文件&#xff0c;插入一张原始图片&#xff0c;1080*1920&#xff0c;如下图&#xff1a; 2&#xff0c;保存时&#xff0c;word 2019默认选项&#xff0c;导致word 保存后&#xff0c;图片…
最新文章