算法:Java计算二叉树从根节点到叶子结点的最大路径和

        要求从根节点到叶子结点的最大路径和,可以通过递归遍历二叉树来实现。对于二叉树中的每个节点,我们都可以考虑包含该节点的最大路径和。在递归的过程中,我们需要不断更新全局最大路径和。

具体的思路

  1. 递归函数设计: 设计一个递归函数,该函数的任务是计算包含当前节点的最大路径和。函数的返回值应该是从当前节点出发到任意叶子节点的最大路径和。

  2. 递归终止条件: 在递归函数中,需要处理递归的终止条件。当当前节点为 null 时,返回 0,表示空路径的和为 0。

  3. 递归计算左右子树的最大路径和: 对于当前节点,递归计算左右子树的最大路径和。如果子树的最大路径和为负数,可以选择不包含该子树,将其贡献值设为 0。

  4. 更新全局最大路径和: 在递归的过程中,不断更新全局最大路径和。全局最大路径和是包含当前节点值的最大路径和,可能由左子树、右子树和当前节点共同组成。

  5. 返回当前子树的最大路径和: 在递归函数的最后,返回当前子树的最大路径和。

代码示例

class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}
}public class MaxPathSum {int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {if (root == null) {return 0;}// 递归计算左右子树的最大路径和int leftMax = Math.max(maxPathSum(root.left), 0);int rightMax = Math.max(maxPathSum(root.right), 0);// 更新全局最大路径和maxSum = Math.max(maxSum, root.val + leftMax + rightMax);// 返回当前子树的最大路径和(只能选择左子树或右子树)return root.val + Math.max(leftMax, rightMax);}public static void main(String[] args) {MaxPathSum solution = new MaxPathSum();// 构造一棵二叉树(示例)TreeNode root = new TreeNode(10);root.left = new TreeNode(2);root.right = new TreeNode(10);root.left.left = new TreeNode(20);root.left.right = new TreeNode(-15);root.right.right = new TreeNode(20);root.left.left.left = new TreeNode(-20);root.right.right.left = new TreeNode(3);root.right.right.right = new TreeNode(-4);int result = solution.maxPathSum(root);System.out.println("最大路径和: " + result);}
}

小结

这个实现中,maxPathSum 方法返回的是以当前节点为根的最大路径和。在递归的过程中,不断更新 maxSum 变量,最终得到整棵树的最大路径和。

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

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

相关文章

蓝桥杯day02——第三大的数

题目 给你一个非空数组,返回此数组中 第三大的数 。如果不存在,则返回数组中最大的数。 示例 1: 输入:[3, 2, 1] 输出:1 解释:第三大的数是 1 。 示例 2: 输入:[1, 2] 输出&…

02-鸿蒙学习之4.0todoList练习

02-鸿蒙学习之4.0todoList练习 代码 /*** 1:组件必须使用Component装饰* 2.Entry 装饰哪个组件,哪个组件就呈现在页面上* 3.被Entry 装饰的入口组件。build()必须有且仅有一个根 ** 容器 ** 组件* 其他的自定义组件,build() 中…

详解API开发【电商平台API封装商品详情SKU数据接口开发】

1、电商API开发 RESTful API的设计 RESTful API是一种通过HTTP协议发送和接收数据的API设计风格。它基于一些简单的原则,如使用HTTP动词来操作资源、使用URI来标识资源、使用HTTP状态码来表示操作结果等等。在本文中,我们将探讨如何设计一个符合RESTfu…

Re54:读论文 How Context Affects Language Models‘ Factual Predictions

诸神缄默不语-个人CSDN博文目录 诸神缄默不语的论文阅读笔记和分类 论文名称:How Context Affects Language Models’ Factual Predictions ArXiv网址:https://arxiv.org/abs/2005.04611 2020年AKBC论文,作者来自脸书和UCL。 本文主要关注…

vscode Markdown 预览样式美化多方案推荐

优雅的使用 vscode写 Markdown,预览样式美化 1 介绍 我已经习惯使用 vscode 写 markdown。不是很喜欢他的 markdown 样式,尤其是代码块高亮的样式。当然用 vscode 大家基本上都会选择安装一个Markdown-preview-enhanced的插件,这个插件的确…

【C++】了解模板

这里是目录 前言函数模板函数模板的实例化类模板 前言 如果我们要交换两个数字,那么我们就需要写一个Swap函数来进行交换,那如果我们要交换char类型的数据呢?那又要写一份Swap的函数重载,参数的两个类型是char,那我们…

Python——— 函数大全

(一)初识函数 函数是可重用的程序代码块。 函数的作用,不仅可以实现代码的复用,更能实现代码的一致性。一致性指的是,只要修改函数的 代码,则所有调用该函数的地方都能得到体现。 在编写函数时&#xff0…

Linux常用命令----mkdir命令

文章目录 1. 基础概念2. 参数含义3. 常见用法4. 实例演示5. 结论 在Linux操作系统中,mkdir 命令是用来创建目录的基础命令。这个命令简单但极其强大,是每个Linux用户都应当熟悉的工具之一。以下是对mkdir命令的详细介绍,包括其参数含义、常见…

苹果cms搭建教程附带免费模板

准备工作: 一台服务器域名源码安装好NGINX+PHP7.0+MYSQL5.5 安装php7.0的扩展,fileinfo和 sg11,不安装网站会搭建失败。 两个扩展都全部安装好了之后 点击-服务-重载配置 这样我们的网站环境就配置完成啦 下载苹果cms 苹果cms程序github链接:选择mac10!下载即可 http…

Vue批量全局处理undefined和null转为““ 空字符串

我们在处理后台返回的信息,有的时候返回的是undefined或者null,这种字符串容易引起用户的误解,所以需要我们把这些字符串处理一下。 如果每个页面都单独处理,那么页面会很冗余,并且后期如果有修改容易遗漏&#xff0c…

DiSC沟通法,如何提高项目沟通效率?

DISC模型是一种用于理解和改善人际沟通的工具,它可以帮助团队成员更好地理解自己和他人的沟通方式,从而提高团队的沟通效率和协作效率。如果双方没有理解和适应对方的行为风格,往往容易造成误解甚至冲突,从而不利于团队间沟通协作…

vscode集成git

1、首先电脑要安装git 打开git官网地址:Git进行下载,如下图界面: 如图片中描述:一般进入官网后会识别电脑对应系统(识别出了我的电脑是Windows系统 。如果未识别到电脑系统,可在左侧选择自己电脑对应的系统…

Influx集群解决方案(Influx Proxy篇)

InFluxDB 集群搭建 本次搭建使用influx proxy 介绍 github地址:https://github.com/chengshiwen/influx-proxy/ Influx Proxy 是一个基于高可用、一致性哈希的 InfluxDB 集群代理服务,实现了 InfluxDB 高可用集群的部署方案, 具有动态扩/缩容、故障恢复…

【MySQL】JDBC编程

👑专栏内容:MySQL⛪个人主页:子夜的星的主页💕座右铭:前路未远,步履不停 目录 一、JDBC工作原理二、JDBC 使用1、准备工作2、使用实例3、手动输入 一、JDBC工作原理 JDBC是Java语言中用于与数据库进行交互…

Panalog 日志审计系统 前台RCE漏洞复现

0x01 产品简介 Panalog是一款日志审计系统,方便用户统一集中监控、管理在网的海量设备。 0x02 漏洞概述 Panalog日志审计系统 sy_query.php接口处存在远程命令执行漏洞,攻击者可执行任意命令,接管服务器权限。 0x03 复现环境 FOFA&#xf…

centos7配置tomcat

简介 Tomcat是一个使用Java编写的开源Web应用服务器,是由Apache Software Foundation管理的一个项目。它是一个轻量级的应用服务器,可以下载、安装和使用,而且还提供了许多高级功能,例如支持Java Servlet、JavaServer Pages (JSP)和JavaServer Faces (JSF) 等JavaEE技术,…

深度解析 Spring Security 自定义异常失效问题:源码剖析与解决方案

🚀 作者主页: 有来技术 🔥 开源项目: youlai-mall 🍃 vue3-element-admin 🍃 youlai-boot 🌺 仓库主页: Gitee 💫 Github 💫 GitCode 💖 欢迎点赞…

计算机视觉面试题-03

1、简单介绍一下sigmoid,relu,softplus,tanh,RBF及其应用场景 这里简单介绍几个激活函数及其应用场景: Sigmoid 函数(Logistic 函数): 公式: s i g m a ( x ) 1 1 e …

Python生成exe文件

Python如何生成exe文件 在终端执行 pip install pyinstaller 在终端执行pyinstaller E:\fund_data\GetFund.py,运行结束后会在D:\Python\Python311\Scripts\dist\目录下生成GetFund.exe文件 3.双击exe文件运行,如果未出现预期结果,可以把e…

2023.11.23使用flask实现在指定路径生成文件夹操作

2023.11.23使用flask实现在指定路径生成文件夹操作 程序比较简单,实现功能: 1、前端输入文件夹 2、后端在指定路径生成文件夹 3、前端反馈文件夹生成状态 main.py from flask import Flask, request, render_template import osapp Flask(__name__)a…