力扣124. 二叉树中的最大路径和(java DFS解法)

Problem: 124. 二叉树中的最大路径和

文章目录

  • 题目描述
  • 思路
  • 解题方法
  • 复杂度
  • Code

题目描述

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

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

给你一个二叉树的根节点 root ,返回其 最大路径和 。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

思路

按递归的处理思想将该问题分解成如下最小子问题:

1.分别求取左右子树的最大节点值之和,合并得到整个树的最大节点值之和(每个节点值,我们称其为对最终最大节点值之和的贡献)。
2.具体的分解处理中:

2.1空节点的最大贡献值为0;
2.2非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和(对于叶节点而言,最大贡献值等于节点值)。

解题方法

1.维护一个全局变量 maxSum 存储最大路径和,在递归过程中更新 maxSum 的值;
2.递归计算左右子节点的最大贡献值,只有在最大贡献值大于 0 时,才会选取对应子节点.(递归函数返回当前节点值加其左右子树的最大节点值之和)
3.在归的过程中,记录当前节点的最大路径和与maxSum比较,取二者中的较大值并更新maxSum

复杂度

时间复杂度:

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 maxSum = Integer.MIN_VALUE;/*** Return the max path of a binary tree** @param root The root node of a binary tree* @return int*/public int maxPathSum(TreeNode root) {maxGain(root);return maxSum;}/*** Get the max path of a binary tree** @param node The node of a binary tree* @return int*/public int maxGain(TreeNode node) {if (node == null) {return 0;}/*(1).Recursively calculates the maximum contribution valueof the left and right child nodes(2).Only when the maximum contribution value is greater than 0,the corresponding child node is selected*/int leftGain = Math.max(maxGain(node.left), 0);int rightGain = Math.max(maxGain(node.right), 0);//The maximum path sum of a node depends on the value of this node// and the maximum contribution of nodes around this nodeint priceNewPath = node.val + leftGain + rightGain;//Update the max pathmaxSum = Math.max(maxSum, priceNewPath);return node.val + Math.max(leftGain, rightGain);}
}

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

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

相关文章

数据结构学习笔记——广义表

目录 一、广义表的定义二、广义表的表头和表尾三、广义表的深度和长度四、广义表与二叉树(一)广义表表示二叉树(二)广义表表示二叉树的代码实现 一、广义表的定义 广义表是线性表的进一步推广,是由n(n≥0&…

pytest自动化框架之allure测试报告的用例描述设置

allure测试报告的用例描述相关方法;如下图 allure标记用例级别severity 在做自动化测试的过程中,测试用例越来越多的时候,如果执行一轮测试发现了几个测试不通过,我们也希望能快速统计出缺陷的等级。 pytest结合allure框架可以对…

网络调试助手 连接Onenet 多协议接入平台 TCP透传协议

onenet文档链接 多协议接入地址 打开Onenet平台,多协议接入 选择TCP透传协议,点击添加产品,输入信息,点击确认 点击设备列表,添加设备 下面需要上传一个解析脚本文件该文件的下载地址lua文件下载地址 建立连接 设备…

接口测试 —— 接口测试的意义

1、接口测试的意义(优势) (1)更早的发现问题: 不少的测试资料中强调,测试应该更早的介入到项目开发中,因为越早的发现bug,修复的成本越低。 然而功能测试必须要等到系统提供可测试…

卷积神经网络(CNN):乳腺癌识别.ipynb

文章目录 一、前言一、设置GPU二、导入数据1. 导入数据2. 检查数据3. 配置数据集4. 数据可视化 三、构建模型四、编译五、训练模型六、评估模型1. Accuracy与Loss图2. 混淆矩阵3. 各项指标评估 一、前言 我的环境: 语言环境:Python3.6.5编译器&#xf…

智能优化算法应用:基于阿基米德优化算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用:基于阿基米德优化算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于阿基米德优化算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.阿基米德优化算法4.实验参数设定5.算…

基础堆溢出原理与DWORD SHOOT实现

堆介绍 堆的数据结构与管理策略 程序员在使用堆时只需要做三件事情:申请一定大小的内存,使用内存,释放内存。 对于堆管理系统来说,响应程序的内存使用申请就意味着要在"杂乱"的堆区中"辨别"出哪些内存是正在…

2023年12月4日:多继承

代码 #include <iostream>using namespace std;class Sofa { private:string sit;int *len; public:Sofa(){cout << "Sofa::无参构造函数" << endl;}Sofa(string sit,int len):sit(sit),len(new int(len)){cout << "Sofa::有参构造函数…

堆的应用:堆排序

文章目录 前言堆排序的实现&#xff08;升序为例&#xff09;代码 前言 堆排序&#xff0c;顾名思义是一个利用堆来完成排序的一个操作。在之前&#xff0c;小编在[C语言学习系列–&#xff1e;【关于qsort函数的详解以及它的模拟实现】] 谈到冒泡排序&#xff0c;但是冒泡排序…

7. 系统信息与系统资源

7. 系统信息与系统资源 1. 系统信息1.1 系统标识 uname()1.2 sysinfo()1.3 gethostname()1.4 sysconf() 2. 时间、日期2.1 Linux 系统中的时间2.1.1 Linux 怎么记录时间2.1.2 jiffies 的引入 2.2 获取时间 time/gettimeofday2.2.1 time()2.2.2 gettimeofday() 2.3 时间转换函数…

登录校验过滤器

会话技术 JWT令牌 过滤器Filter 拦截器 interceptor cookise package com.it.controller;import com.it.pojo.Result; import lombok.extern.slf4j.Slf4j; import org.springframework.web.bind.annotation.GetMapping; import org.springframework.web.bind.annotation.Re…

Golang 设置运行的cpu数与channel管道

介绍&#xff1a;为了充分了利用多cpu的优势&#xff0c;在Golang程序中&#xff0c;设置运行的cpu数目。 func main() {//获取系统当前cpu的数量num : runtime.NumCPU()//这里根据需求来设置整个go程序去使用几个cpuruntime.GOMAXPROCS(num)fmt.Println("num ", nu…

室内外融合便携式定位终端5G+UWB+RTK

一、介绍 便携式定位终端主要用于提供高精度的位置数据&#xff0c;支持室内UWB定位和室外北斗系统定位功能&#xff0c;支持5G公网和5G专网通信功能&#xff0c;便携式定位终端中超宽带(UWB)和实时动态(RTK)技术的集成代表了精确位置跟踪方面的重大进步。这款UWBRTK便携式定位…

Windows开启SQL Server服及1433端口

需求&#xff1a;Windows开启SQL Server服务及1433端口 目前端口没有启动 解决&#xff1a; 打开SQL Server配置管理器&#xff08;winR&#xff09; 各个sqlserver版本在textbox中输入对应的命令如下&#xff1a; SQLServerManager15.msc&#xff08;对于 SQL Server 2019 &am…

python获取阿里云云解析dns的域名解析记录

最近由于工作原因接触到阿里云的服务&#xff0c;我需要实时获取所有的域名信息&#xff0c;用于对其进行扫描&#xff0c;因此写了一个自动化爬取脚本 给需要的人分享。 &#xff08;阿里云有官方的demo&#xff0c;有兴趣的可以自己看一下&#xff0c;后面也会放链接&#xf…

高级/进阶”算法和数据结构书籍推荐

“高级/进阶”算法和数据结构书籍推荐《高级算法和数据结构》 高级算法和数据结构 为什么要选择本书 谈及为什么需要花时间学算法&#xff0c;我至少可以列举出三个很好的理由。 (1)性能&#xff1a;选择正确的算法可以显著提升应用程序的速度。仅就搜索来说&#xff0c;用二…

人工智能发展史

人工智能&#xff08;AI&#xff09;的发展史是一段跨越数十年的旅程&#xff0c;涵盖了从早期理论探索到现代技术革新的广泛内容。人工智能的发展历程展示了从最初的概念探索到现代技术突破的演变。尽管经历了多次起伏&#xff0c;但AI领域持续进步&#xff0c;不断拓展其应用…

2243:Knight Moves

文章目录 题目描述思路1. DFS2. BFS3. 动态规划 解题方法1. DFS2. BFS3. 动态规划 题目描述 题目链接 翻译如下&#xff1a; 注&#xff1a;骑士移动是和象棋里的马一样走的是日字型 你的一个朋友正在研究旅行骑士问题 &#xff08;TKP&#xff09;&#xff0c;你要找到最短的…

Android 断点调试

Android 调试 https://developer.android.google.cn/studio/debug?hlzh-cn 调试自己写的代码&#xff08;不在Android源码&#xff09; 点击 Attach debugger to Android process 图标 需要在添加断点界面手动输入函数名 但也可以不手动&#xff0c;有个技巧可以new 空proje…

个人博客搭建保姆级教程-HTML页面编写篇

选择模板 首先我们要选一个好的模板&#xff0c;然后对模板进行剪裁。我的模板是在站长之家进行下载的 素材下载-分享综合设计素材免费下载的平台-站长素材 我选的模板的具体地址是 个人博客资讯网页模板 这里需要我们学习一下在前边一篇文章里提到的HTML、JavaScript、CSS…