力扣每日一题124:二叉树中的最大路径和

题目

困难

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

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

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

示例 1:

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

示例 2:

输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42

提示:

  • 树中节点数目范围是 [1, 3 * 104]
  • -1000 <= Node.val <= 1000

面试中遇到过这道题?

1/5

通过次数

410.4K

提交次数

901.1K

通过率

45.5%

思路

按照题目对路径的定义,一个结点可以连接他的左子树结点和他的右子树结点。

若左子树的路径大于0,则说明左子树的路径对根节点的路径和有增大的帮助,这是可以加上左子树的路径和。

对于右子树,也是一样的。

左右子树对路径和的帮助加上根节点的值就是以该节点为根的数的最大路径和。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxsum=-1000000000;
    int maxpath(TreeNode* root)
    {
        if(!root) return 0;
        //左右子树的最大贡献,大于零才有贡献
        int leftmax=max(maxpath(root->left),0);
        int rightmax=max(maxpath(root->right),0);
        maxsum=max(maxsum,(leftmax+rightmax+root->val));
        //该节点的最大贡献
        return root->val+max(leftmax,rightmax);
    }
    int maxPathSum(TreeNode* root) {
        maxpath(root);
        return maxsum;
    }
};

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

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

相关文章

08.3.grafana自定义图形

grafana自定义图形 找插件里面的zabbix 点击update 数据源—zabbix数据源,添加zabbix数据源 选择zabbix类型 我这里配置的是本地&#xff0c;所以URL直接localhost 这里配置zabbix登录账号密码Admin/zabbix 然后点击保存并测试&#xff0c;会直接显示版本 导入模板&…

电影网站|基于SSM+vue的电影网站系统(源码+数据库+文档)

电影网站 目录 基于SSMvue的电影网站系统 一、前言 二、系统设计 三、系统功能设计 1 系统功能模块 2 管理员功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介绍&#xff1a;✌️大厂码农|毕设布道…

虚拟机CentOS密码重置

1&#xff0c;reboot重启 在出现下面的界面1按e 如果有选项就选择“CentOS Linux &#xff08;3.10.0-327.e17.x86_64&#xff09;7 &#xff08;Core&#xff09;”【我的电脑没有直接显示界面2】 界面1 界面2 2&#xff0c;在上述界面2中继续按e进入编辑模式 找到“ro cr…

vue2和vue3区别: 探索关键差异

vue2和vue3区别&#xff1a; 探索关键差异 Vue.js 作为流行的前端框架&#xff0c;其版本 3 带来了许多令人兴奋的改进和新功能。虽然 Vue 3 保持了与 Vue 2 的相似性&#xff0c;但也存在一些关键差异需要开发者注意。本文将通过表格形式&#xff0c;清晰地展现 Vue 2 和 Vue …

文献阅读——LPPLS(2)

A study on the bursting point of Bitcoin based on the BSADF and LPPLS methods 文献来源[2] Yao, Can-Zhong, and Hong-Yu Li. “A study on the bursting point of Bitcoin based on the BSADF and LPPLS methods.” The North American Journal of Economics and Financ…

Istio 使用 Apache SkyWalking 进行服务链路追踪、链路监控告警

一、Istio 使用 Apache SkyWalking 链路追踪和告警 SkyWalking是一个开源的观测平台&#xff0c;用于从服务和云原生等基础设施中收集、分析、聚合以及可视化数据&#xff0c;SkyWalking 提供了一种简便的方式来清晰地观测分布式系统&#xff0c;甚至可以观测横跨不同云的系统…

PyCharm粘贴失灵?一文教你快速恢复!(如何解决Pycharm无法粘贴的问题)

文章目录 💢 问题 💢🏡 演示环境 🏡💯 解决方案 💯⚓️ 相关链接 ⚓️💢 问题 💢 "为什么你的代码编辑器突然变得不听话了?"最近在使用pycharm的时候遇到了一个问题,就是在pycharm中无法使用粘贴功能,后面经过一番折腾得到了解决,现在将我的解决…

03、SpringBoot 源码分析 - SpringApplication启动流程三

SpringBoot 源码分析 - SpringApplication启动流程三 初始化基本流程SpringApplication的setListeners设置监听器deduceMainApplicationClass对端主启动类rungetRunListeners获取SpringApplicationRunListener监听器EventPublishingRunListener的构造方法SimpleApplicationEven…

第十二篇:数据库系统导论 - 探索数据管理的基石

数据库系统导论 - 探索数据管理的基石 1 引言 数据的力量&#xff1a;揭秘数据库系统的核心 在信息时代&#xff0c;数据无处不在&#xff0c;它们成为了企业和社会运作的基础。我们如何储存、检索、更新和维护这些数据&#xff0c;决定了我们能否从这些数据中获得力量。数据…

C语言深入理解指针(4)--指针笔试题解析

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 C语言深入理解指针(4) 收录于专栏【C语言学习】 本专栏旨在分享学习C语言学习的一点学习笔记&#xff0c;欢迎大家在评论区交流讨论&#x1f48c; 目录 1. size…

[嵌入式系统-75]:RT-Thread-快速上手:正点原子探索者 STM32F407示例

目录 正点原子探索者 STM32F407 上手指南 1. 简介 2. 准备工作 3. 运行第一个示例程序 3.1 编译下载 3.2 运行 继续学习 正点原子探索者 STM32F407 上手指南 1. 简介 探索者 STM32F407 是正点原子推出的一款基于 ARM Cortex-M4 内核的开发板&#xff0c;最高主频为 16…

启用dell服务器的iDRAC

插网线 观察到 dell服务器背板左侧有一个网口&#xff0c;标有iDRAC字样&#xff0c;使用网线将该网口和网段所在的交换机连接起来。 网络配置 重启计算机&#xff0c;依照屏幕显示按F2进入SystemSetup。选择iDRACsettings – Network&#xff0c;需要改动的如下&#xff08;现…

WPS表格:使用vlookup函数解决乱序数据对应问题

我们常常会遇到两个表格的内容相同&#xff0c;但是顺序不一致的情况。并且这种顺序无关于简单的排序&#xff0c;而是一种业务性很强的复杂排序规则。下面我举个例子&#xff0c;使用VLOOKUP复制数据。 假设太阳系行星举办了一次卖萌比赛&#xff0c;由太阳妈妈决定谁是最萌的…

Java | Leetcode Java题解之第84题柱状图中最大的矩形

题目&#xff1a; 题解&#xff1a; class Solution {public int largestRectangleArea(int[] heights) {int n heights.length;int[] left new int[n];int[] right new int[n];Arrays.fill(right, n);Deque<Integer> mono_stack new ArrayDeque<Integer>();f…

【git】通过JetBrains IDE对git的操作

应该适用于所有jetbrains产品。 一、拉取(pull)代码 上方工具栏-Git-克隆。然后填写git地址与本地存放地址。 二、搁置 修改代码后搁置代码&#xff08;不提交&#xff0c;但是也不撤销已修改的代码&#xff0c;把它暂存起来&#xff09;。 界面的左上角。1->2->3。…

[算法][差分数组][leetcode]1094. 拼车

地址&#xff1a; https://leetcode.cn/problems/car-pooling/description/ 解法一&#xff1a;暴力解法 class Solution {public boolean carPooling(int[][] trips, int capacity) {//特殊条件判断if(nulltrips||capacity<0){return false;}int [] d new int[1001];//暴…

Web自动化-日志收集

目标 1. 理解日志的相关概念 2. 掌握日志的基本用法 3. 掌握日志的高级用法 一、日志相关概念 目标 1. 了解日志的概念 2. 理解日志的作用 3. 掌握常见的日志级别 1. 日志 概念&#xff1a;日志就是用于记录系统运行时的信息&#xff0c;对一个事件的记录&#xff1b…

Qt---信号和槽

一、信号和槽机制 所谓信号槽&#xff0c;实际就是观察者模式。当某个事件发生之后&#xff0c;比如&#xff0c;按钮检测到自己被点击了一下&#xff0c;它就会发出一个信号&#xff08;signal&#xff09;。这种发出是没有目的的&#xff0c;类似广播。如果有对象对这个信号…

SpringBoot自定义初始化sql文件 支持多类型数据库

我在resources目录下有init.sql初始化sql语句 指定sql文件的地址 sql内容如下&#xff1a; /*角色表*/ INSERT INTO #{schema}ccc_base_role (id, create_time, create_user_id, is_delete, role_name, status, update_time, update_user_id) VALUES(b89e30d81acb88448d412…

2024数据分析管理、数字经济与教育国际学术会议(ICDAMDEE2024)

2024数据分析管理、数字经济与教育国际学术会议(ICDAMDEE2024) 会议简介 2024年数据分析管理、数字经济和教育国际学术会议&#xff08;ICDAMDEE 2024&#xff09;将在武汉举行。会议不仅展示了来自世界各地的研究专家围绕数据分析管理、数字经济和教育的最新科研成果&#xf…