当前位置: 首页 > 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; 数据…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

MLP实战二:MLP 实现图像数字多分类

任务 实战&#xff08;二&#xff09;&#xff1a;MLP 实现图像多分类 基于 mnist 数据集&#xff0c;建立 mlp 模型&#xff0c;实现 0-9 数字的十分类 task: 1、实现 mnist 数据载入&#xff0c;可视化图形数字&#xff1b; 2、完成数据预处理&#xff1a;图像数据维度转换与…...

自定义线程池1.2

自定义线程池 1.2 1. 简介 上次我们实现了 1.1 版本&#xff0c;将线程池中的线程数量交给使用者决定&#xff0c;并且将线程的创建延迟到任务提交的时候&#xff0c;在本文中我们将对这个版本进行如下的优化&#xff1a; 在新建线程时交给线程一个任务。让线程在某种情况下…...