当前位置: 首页 > news >正文

面试算法51:节点值之和最大的路径

题目

在二叉树中将路径定义为顺着节点之间的连接从任意一个节点开始到达任意一个节点所经过的所有节点。路径中至少包含一个节点,不一定经过二叉树的根节点,也不一定经过叶节点。给定非空的一棵二叉树,请求出二叉树所有路径上节点值之和的最大值。例如,在如图8.6所示的二叉树中,从节点15开始经过节点20到达节点7的路径的节点值之和为42,是节点值之和最大的路径。
在这里插入图片描述

分析

这个题目中二叉树路径的定义又和前面的不同。这里的路径最主要的特点是路径有可能同时经过一个节点的左右子节点。例如,在图8.6中,一条路径可以经过节点15、节点20和节点7,即节点20的左子节点15和右子节点7同时在一条路径上。当然,路径也可以不同时经过一个节点的左右子节点。例如,在图8.6中,一条路径可以经过节点-9、节点20、节点15和节点-3。

也就是说,当路径到达某个节点时,该路径既可以前往它的左子树,也可以前往它的右子树。但如果路径同时经过它的左右子树,那么就不能经过它的父节点。

由于路径可能只经过左子树或右子树而不经过根节点,为了求得二叉树的路径上节点值之和的最大值,需要先求出左右子树中路径节点值之和的最大值(左右子树中的路径不经过当前节点),再求出经过根节点的路径节点值之和的最大值,最后对三者进行比较得到最大值。由于需要先求出左右子树的路径节点值之和的最大值,再求根节点,这看起来就是后序遍历。

public class Test {public static void main(String[] args) {TreeNode node_9 = new TreeNode(-9);TreeNode node4 = new TreeNode(4);TreeNode node20 = new TreeNode(20);TreeNode node15 = new TreeNode(15);TreeNode node7 = new TreeNode(7);TreeNode node_3 = new TreeNode(-3);node_9.left = node4;node_9.right = node20;node20.left = node15;node20.right = node7;node15.left = node_3;int result = maxPathSum(node_9);System.out.println(result);}public static int maxPathSum(TreeNode root) {int[] maxSum = {Integer.MIN_VALUE};dfs(root, maxSum);return maxSum[0];}private static int dfs(TreeNode root, int[] maxSum) {if (root == null) {return 0;}int[] maxSumLeft = {Integer.MIN_VALUE};int left = Math.max(0, dfs(root.left, maxSumLeft));int[] maxSumRight = {Integer.MIN_VALUE};int right = Math.max(0, dfs(root.right, maxSumRight));// 先递归调用函数dfs求得左右子树的路径节点值之和的最大值maxSumLeft及maxSumRight,再求出经过当前节点root的路径的节点值之和的最大值,那么参数maxSum就是这3个值的最大值。maxSum[0] = Math.max(maxSumLeft[0], maxSumRight[0]);maxSum[0] = Math.max(maxSum[0], root.val + left + right);// 先,left代表左树,right代表右树return root.val + Math.max(left, right);// 后,是子树的行为,不是本身这个节点的行为}
}

相关文章:

面试算法51:节点值之和最大的路径

题目 在二叉树中将路径定义为顺着节点之间的连接从任意一个节点开始到达任意一个节点所经过的所有节点。路径中至少包含一个节点,不一定经过二叉树的根节点,也不一定经过叶节点。给定非空的一棵二叉树,请求出二叉树所有路径上节点值之和的最…...

阿里云 k8s 容器服务 设置节点为不可调度的两种方法有什么区别?

两种方法的区别在于:drain 会驱逐原来节点上的所有 pod,而 cordon 只是停止调度, 禁止新的 pod 调度进来,但旧的 pod 不会受影响。...

新一代数据质量平台datavines

在我实习的第一家公司的时候,有幸参与Apache Griffin的开发,也先后在一起其他公司使用过数据质量平台,同时也调研过一些开源的数据质量平台。 最近和朋友一起参与开发了datavines数据质量平台,随着在数据行业越呆越久&#xff0c…...

建议收藏《2023华为海思实习笔试-数字芯片真题+解析》(附下载)

华为海思一直以来是从业者想要进入的热门公司。但是岗位就那么多,在面试的时候,很多同学因为准备不充分,与岗位失之交臂,无缘进入该公司。今天为大家带来《2023华为海思实习笔试-数字芯片真题解析》题目来源于众多网友对笔试的记录…...

【详细教程】关于如何使用GitGitHub的基本操作汇总GitHub的密钥配置 ->(个人学习记录笔记)

文章目录 1. Git使用篇1.1 下载安装Git1.2 使用Git 2. GitHub使用篇2.1 如何git与GitHub建立联系呢?2.2 配置公钥 1. Git使用篇 1.1 下载安装Git 点击 官网链接 后,进入Git官网,下载安装包 然后根据系统类型进行下载,一般为wind…...

HTML样式CSS、图像

HTML样式-CSS: CSS (Cascading Style Sheets) 用于渲染HTML元素标签的样式。CSS可以通过以下方式添加到HTML中&#xff1a;1&#xff09;、内联方式&#xff1a;在HTML元素中使用“style”属性&#xff1b;2&#xff09;、内部样式表&#xff1a;在HTML文档头部<head>区…...

智能电表瞬时电量是什么意思?

智能电表已经成为我们进行能源管理的重要工具。其中&#xff0c;瞬时电量这一概念逐渐走进大众视野。那么&#xff0c;智能电表瞬时电量究竟是什么意思&#xff1f;它对我们的生活和能源管理又有哪些影响呢&#xff1f;下面&#xff0c;小编就来为大家介绍一下瞬时电量&#xf…...

Redis之 redis.config配置文件

文章目录 前言一、基本配置1.单位2.包含3.网络配置4.通用5.快照6.安全7.限制8.仅追加模式 二、总体主要介绍总结 前言 行家一出手&#xff0c;就知有没有&#xff0c;让一起学习redis.config配置文件。 一、基本配置 Redis 的配置文件位于 Redis 安装目录下&#xff0c;文件名…...

BIOS开发笔记 - CMOS

CMOS原来指的是一种生产电子电路的工艺,在PC上一般指的是RTC电路单元,因为早期它是由这种工艺生产出来的,所以又把RTC称作了CMOS。 RTC(Real Time Clock)即实时时钟,用于保存记录时间和日期,也可以用来做定时开机功能。RTC靠一组独立的电源给它供电,这样设计的目的就是…...

leetcode_117 填充每个节点的下一个右侧节点指针 II

文章目录 1. 题意2. 题解2.1 BFS2.2 BFS空间优化2.3 DFS序层次记录 3. Ref 1. 题意 在一颗树的同层之间用指针把他们链接起来。 填充每个节点的下一个右侧节点指针 II 2. 题解 2.1 BFS 用一个变量记录下同层最右侧的节点&#xff0c;当遍历到时更新下一层的最右侧节点即可…...

亲测 IDEA Pycharm 全家桶 自动重置免费30天

理论上是通用的 插件市场安装 添加第三方插件仓库地址 在Settings/Preferences... -> Plugins 内手动添加第三方插件仓库地址&#xff1a;https://plugins.zhile.io 搜索&#xff1a;IDE Eval Reset插件进行安装。如果搜索不到请注意是否做好了上一步&#xff1f;网络是否…...

Marp: 将 Markdown 变为 PPT 式样的 VScode 插件

样例代码&#xff1a; --- marp: true size: 16:9 theme: default header: footer: --- <!-- _footer: Jia ming<br>Gansu University of Political Science and Law --> <!-- _backgroundColor: lightskyblue --> ## <!-- fit --> 笔记检验概述>…...

根据正则表达式截取字串符,这个办法打败99%程序员

作为一名程序员&#xff0c;常常会在以下情况下使用函数功能根据正则表达式截取字符串&#xff1a; 1.字符串处理&#xff1a;当需要使用正则表达式匹配和提取字符串中的特定模式时&#xff0c;可以使用该函数。例如&#xff0c;从一段文本中提取电子邮件地址、电话号码或网站…...

冬天女儿的羽绒服就选它了,哈哈很喜欢

长款设计感满满的羽绒服 真的一下子就戳中了我的心巴 90白鸭绒&#xff0b;杜邦三防工艺&#xff0b;精细压线 厚实保暖不臃肿&#xff0c;粉色撞色甜美又可爱...

Vim插件配置

工欲善其事&#xff0c;必先利其器&#xff0c;倒腾一下vim的配置&#xff0c;做个记录。 ".vimrc里的内容&#xff1a;""for base configure set t_Co256 if ! has("gui_running")set t_Co256 endifif &diffhighlight DiffAdd ctermbold cte…...

函数参数的最佳传递方式与现代C++的规则

函数参数的最佳传递方式与现代C的规则 在C中&#xff0c;如何最佳地传递函数参数以及如何处理类的特殊成员函数&#xff0c;一直是优化性能和代码质量的重要话题。下面我将详细解释这些概念。 使用移动语义实现 Swap 函数 移动语义&#xff08;Move Semantics&#xff09;能…...

Asterisk Ubuntu 安装

更新环境 sudo apt update sudo apt install wget build-essential git autoconf subversion pkg-config libtool sudo contrib/scripts/get_mp3_source.sh A addons/mp3 A addons/mp3/common.c A addons/mp3/huffman.h A addons/mp3/tabinit.c A addons/mp3/Ma…...

rwkv模型lora微调之accelerate和deepspeed训练加速

目录 一、rwkv模型简介 二、lora原理简介 三、rwkv-lora微调 1、数据整理 2、环境搭建 a、Dockerfile编写 b、制造镜像 c、容器启动 3、训练代码修改 四、模型推理 1、模型推理 2、lora权重合并 3、推理web服务 五、总结 由于业务采用的ChatGLM模型推理成本太大了…...

分享一下在微信小程序里怎么做一个投票链接

在当今信息化社会&#xff0c;投票已成为各行各业收集意见、汇聚智慧的重要手段。传统的投票方式往往需要投入大量人力物力&#xff0c;而如今&#xff0c;借助微信小程序&#xff0c;我们可以在几分钟内创建一个高效、便捷的投票平台。本文将详细介绍如何在微信小程序中添加投…...

v-model语法糖

v-model原理 v-model实现双向绑定的语法糖&#xff0c;常用于表单与组件之间的数据双向绑定v-model本质上是 value属性和input事件的一层包装 v-model的作用&#xff1a;提供数据的双向绑定数据发生了改变&#xff0c;页面会自动变 v-bind:value页面输入改变 &#xff0c; 数据…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...