力扣题/二叉树/二叉树中的最大路径和

server/2024/9/24 1:49:39/

二叉树中的最大路径和

力扣原题

二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ,返回其 最大路径和 。

示例 1:
在这里插入图片描述

输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6

示例 2:
在这里插入图片描述

输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42

javascript">/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number}*/
var maxPathSum = function(root) {let max = -Number.MAX_VALUE // 递归过程更新最大值function dfs(node) {if(!node) return 0const val = node.valconst leftMax = dfs(node.left)const rightMax = dfs(node.right)// 1. 当前节点最大贡献值 = 当前节点值 + 左子树最大贡献值 + 右子树最大贡献值const sum = val + Math.max(leftMax, 0) + Math.max(rightMax, 0) max = Math.max(max, sum) // 更新最大值if(!node.left && !node.right) {// 2.1. 叶子节点:非负数时作为最大贡献值返回,否则最大贡献值为0return Math.max(val, 0)} else {// 2.2 非叶子节点:  当前节点值 + 取其中的最大值(左子树最大贡献值,右子树最大贡献值)const childMax = Math.max(leftMax, rightMax)return Math.max(val + childMax, 0) // 大于0才选为最大贡献值递归,否则不选相当于0}}dfs(root)return max
};

解题思路

核心思路,把所有节点,都当作只有当前根节点+左子树+右子树
获取节点最大贡献值,和递归的最大贡献值,逻辑不一样。
获取当前节点最大贡献值,相当于以当前节点作为根节点了,最大贡献值就是当前节点加左子树和右子树的最大贡献值
而当往回递归时,当前节点不作为根节点,而是子树,此时递归返回的最大贡献值,只能选择其一,否则就存在分叉了

  1. 要获取当前节点的,最大路径和(以下称为最大贡献值),显而易见得到:
    当前节点最大贡献值 = 当前节点值 + 左子树最大贡献值(非负) + 右子树最大贡献值(非负)

  2. 但是如何保证不出现分叉,那就需要在递归的时候进行限制了,递归条件:
    2.1 叶子节点:非负数时作为最大贡献值返回,否则最大贡献值为0
    2.2 非叶子节点: 当前节点值 + 取其中的最大值(左子树最大贡献值,右子树最大贡献值)


http://www.ppmy.cn/server/101061.html

相关文章

入门 - vue中v-model的实现原理和完整用法详解

v-model介绍 v-model是vue的双向绑定的指令,能将页面上控件输入的值同步更新到相关绑定的data属性,也会在更新data绑定属性时候,更新页面上输入控件的值。在view层,model层相互需要数据交互,即可使用v-model。 双向绑…

数据结构与算法 - 动态规划

1. 斐波那契数列 /*** 要点1:* 从已知子问题的解,推导出当前问题的解* 推倒过程中可以表达为一个数学公式* 要点2:* 用一维或二维数组来保存之前的计算结果(可以进一步优化)** Dynamic-Programming - 由…

Chromium编译指南2024 - Android篇:全新获取源代码(五)

1.引言 在前面的章节中,我们详细介绍了编译 Chromium for Android 所需的系统和硬件要求,以及如何配置基础开发环境和 depot_tools。完成这些准备工作后,下一步就是获取 Chromium 的源代码。获取源代码是编译 Chromium 的关键步骤&#xff0…

两大主流大模型应用开发工具LangChain与LlamaIndex的比较分析

近来,技术的飞速发展将人工智能(AI)和大型语言模型(LLM)领域推向了新的高度。LangChain 和 LlamaIndex 已成为该领域的主要参与者。它们各有自己独特的能力和优势。 本文比较了这两种引人入胜的技术之间的较量&#x…

编码在左,学习在右,你心中的天平如何倾斜?

目录 前言 程序员如何平衡日常编码工作与提升式学习? 养成高效编码习惯 掌握时间管理技巧 提升式学习的策略 广泛涉猎的优势与考虑因素 深入钻研的优势与考虑因素 职业发展与个人成长的和谐共生 结束语 前言 程序员如何平衡日常编码工作与提升式学习&#…

【数据结构与算法 | 图篇】Bellman-Ford算法(单源最短路径算法)

1. 前言 前文的迪杰斯特拉算法不能求解有负边的图的最短路径的问题。而此文的Bellman-Ford可以处理含负权边的图算法,并且能检测出图中是否存在负环(权重和为负数的环). 2. 基本思想 1. 初始化: 对于所有顶点 v ∈ V \ {s}&am…

Java 网络编程练习

InternetExercise1 package InternetExercise20240815;public class InternetExercise1 {public static void main(String[] args) {// 网络编程// 在网络通信协议下,不同计算机上面运行的程序,可以实现不同计算机上的数据传输// 网络编程三要素// 1.IP…

CG-68 冻土传感器 实时温度监测 冻土深度及时了解

产品概述 冻土传感器,也称冻土检测仪。外型轻便,便于携带和连接。由电源模块、温度传感模块、漂零及温度补偿模块、数据处理模块等组成。传感器内置信号采样及放大、漂零及温度补偿功能,用户接口简洁、方便。用于正确分辨土壤冻结状态&#…