力扣hot100 二叉树中的最大路径和 递归

Problem: 124. 二叉树中的最大路径和
在这里插入图片描述

文章目录

  • 解题方法
  • 复杂度
  • 💖 Code

解题方法

👨‍🏫 参考思路
在这里插入图片描述

复杂度

时间复杂度: O ( n ) O(n) O(n)

空间复杂度: O ( n ) O(n) O(n)

💖 Code

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int ans = -20000;//此处的最小值一定要小于数据范围的最小值 -10000public int maxPathSum(TreeNode root){cal(root);return ans;}/*** @param root 当前树的节点* @return 当前树的单侧最大路径长度*/private int cal(TreeNode root){if (root == null)// 访问到叶子节点,返回 0return 0;int l = cal(root.left);// 递归计算左右子树int r = cal(root.right);int max = l > r ? l : r;// 记录左臂右膀的长度int t = root.val;// t 记录的是以当前 root 为转折点的路径长度if (l > 0)// 负数则舍弃t += l;if (r > 0)t += r;int res = root.val;// res = 左右子树单侧路径较长者 + 当前root的值if (max > 0)// 同理,不要负值拖油瓶res += max;ans = Math.max(ans, t);// 更新全局答案return res;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

教你用通义千问只要五步让千年的兵马俑跳上现代的科目三?

教你用五步让千年的兵马俑跳上现代的舞蹈科目三? 上面这个“科目三”的视频,只用了一张我上月去西安拍的兵马俑照片生成的。 使用通义千问,只要5步就能它舞动起来,跳上现在流行的“科目三”舞蹈。 全民舞王 第1步 打开通义千问…

js 回文串

思路: 判断一个字符串是否为回文字符串的基本思路是比较字符串的正序和倒序是否相同。 两者相同,则该字符串是回文字符串,否则不是。 要实现这一思路,我们可以使用 JavaScript 字符串的一些方法。我是忽略了所有的空格和符号&…

【grpc】利用protobuf实现java或kotlin调用python脚本,含实现过程和全部代码

前言 在一些特殊场景中,我们可能需要使用java或者其他任意语言调用python脚本或sdk等。本文的需求衍生也不例外于此,python端有sdk,但只能在python中调用,于是就有了本文章。 常见的调用方式如jython、python提供http rest接口、…

DC电源模块在物联网设备中的关键作用

BOSHIDA DC电源模块在物联网设备中的关键作用 DC电源模块在物联网设备中发挥着关键作用。物联网设备通常需要稳定可靠的电源供应,以保证设备的正常运行。DC电源模块提供了相应的电压和电流输出,为物联网设备提供所需的电力。 具体来说,DC电…

解决英特尔无线网卡WiFi或者蓝牙突然消失问题

winR,输入“devmgmt.msc”,检查设备管理器中的无线网卡驱动是否安装好。 访问https://www.intel.cn/content/www/cn/zh/download/19351/windows-10-and-windows-11-wi-fi-drivers-for-intel-wireless-adapters.html下载对应系统版本的英特尔无线网卡WiFi…

创始人记|2023「年终总结」暨 WorkfineV6版本发布

大家好,我是Workfine黄坤,很高兴能够再次为大家进行分享。衷心感谢大家一直以来对我们的厚爱和支持。新的一年,祝愿大家财源滚滚,身体健康,阖家幸福。 这是我们创业的第七个年头,进入这一行也有整整十年。…

使用 Apache POI 更新/覆盖 特定的单元格

使用 Apache POI 更新特定的单元格 一. 需求二. 实现三. 效果 一. 需求 将以下表中第4行,第4列的单元格由“张宇”更新为“汤家凤”,并将更行后的结果写入新的Excel文件中; 二. 实现 使用Apache POI,可以精确定位到需要更改的单…

Resize:最近邻插值、双线性插值、双三次插值

Resize:最近邻插值、双线性插值、双三次插值 Opencv resize函数1. 最近邻插值(INTER_NEAREST)1.1 原理1.2 代码实例1.3 简单的代码复现1.4 特点 2. 双线性插值(INTER_LINEAR)(默认值)2.1 原理2.…

【React源码 - Diff算法】

介绍 在React学习中,Diff算法(协调算法),想必我们并不陌生,简单来说就是一个对比新老节点寻找差异,然后找出最小的一个变化集,最后对这个最小变化集进行最小的DOM操作,本文将从源码来分析在React(17.0.2)中…

聚观早报 |一加Ace 3鸣沙金开售;地平线征程6将发布

聚观早报每日整理最值得关注的行业重点事件,帮助大家及时了解最新行业动态,每日读报,就读聚观365资讯简报。 整理丨Cutie 1月16日消息 一加Ace 3鸣沙金开售 地平线征程6将发布 互动短剧《谍影成双》首曝PV 台积电发布四季度财报 保时捷…

kafka系列(二)

本章承接kafka一内容,文章在本人博客主页都有,可以自行点击浏览。 幂等性 请求执行多次,但执行的结果是一致的。 如果,某个系统是不具备幂等性的,如果用户重复提交了某个表格,就可能会造成不良影响。例如…

第十讲 单片机驱动彩色液晶屏 控制RA8889软件:图像运算

单片机驱动TFT彩色液晶屏系列讲座 目录 第一讲 单片机最小系统STM32F103C6T6通过RA8889驱动彩色液晶屏播放视频 第二讲 单片机最小系统STM32F103C6T6控制RA8889驱动彩色液晶屏硬件框架 第三讲 单片机驱动彩色液晶屏 控制RA8889软件:如何初始化 第四讲 单片机驱动彩色液晶屏 控…

助力工业焊缝质量检测,YOLOv7【tiny/l/x】不同系列参数模型开发构建工业焊接场景下钢材管道焊缝质量检测识别分析系统

焊接是一个不陌生但是对于开发来说相对小众的场景,在我们前面的博文开发实践中也有一些相关的实践,感兴趣的话可以自行移步阅读即可:《轻量级模型YOLOv5-Lite基于自己的数据集【焊接质量检测】从零构建模型超详细教程》 《基于DeepLabV3Plus…

反向代理的本质是什么?

反向代理是一种网络架构模式,通常用于提供静态内容、处理安全、负载均衡和缓存等任务。在这种架构中,客户端发送的请求首先到达反向代理服务器,然后由反向代理服务器将请求转发给后端的实际服务器。反向代理服务器可以处理和修改请求和响应&a…

20. 从零用Rust编写正反向代理,四层反向代理stream(tcp与udp)实现

wmproxy wmproxy已用Rust实现http/https代理, socks5代理, 反向代理, 静态文件服务器,四层TCP/UDP转发,内网穿透,后续将实现websocket代理等,会将实现过程分享出来,感兴趣的可以一起造个轮子 项目地址 gite: https:…

Linux 下GEO Server发布图层后,中文乱码解决方案

发布的图层,显示中文乱码,都是框框:如“口口” 第一步先查看Linux字符集 如下命令所示: 1.查看当前系统语言 echo $LANG2.查看安装的语言包 locale如果上面的命令执行后显示的是en_US.UTF-8,则说明当前语言系统及安…

创意交融:集成自定义报表和仪表盘设计器,实现图标替换

前言 在现代数据分析领域,随着对报表和数据分析的需求不断增长,市场上涌现了许多嵌入式报表工具。这些工具能够与企业现有的OA、ERP、MES、CRM等应用系统深度集成,实现对业务数据的自助式分析。然而,在实际应用中,不同…

实战 php 使用 wkhtmltopdf 生成pdf的全过程

公司里边有生成pdf报告的业务需求,之前有过尝试用tcpdf,直接生成的pdf的过程,但是pdf报告的内容数据,根据不同内容的变化,都是各种各样的bug,一直处理修修补补的状态,让后台开发人员很是头疼. 经过思索和甄选,总结出我们的业务中是由于样式不可控导致的,当时从逻辑上就思考到用…

QT quick基础:组件gridview

组件gridview与android中gridview布局效果相同。下面记录qt quick该组件的使用方法。 方法一: // ContactModel.qml import QtQuick 2.0ListModel {ListElement {name: "1"portrait: "icons/ic_find.png"}ListElement {name: "2"por…

【iOS】数据存储方式总结(持久化)沙盒结构

在iOS开发中,我们经常性地需要存储一些状态和数据,比如用户对于App的相关设置、需要在本地缓存的数据等等,本篇文章将介绍六个主要的数据存储方式 iOS中数据存储方式(数据持久化) 根据要存储的数据大小、存储数据以及…