leetcode-124. 二叉树中的最大路径和(树形dp)

leetcode-124. 二叉树中的最大路径和(树形dp)原题链接路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ,返回其 最大路径和 。示例 1:输入:root = [1,2,3]输出:6解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6示例 2:输入:root = [-10,9,20,null,null,1

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接

路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。

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

给你一个二叉树的根节点 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
 

提示:

树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution { 
   
public:
    const int INF = 0x3f3f3f3f;
    int res = -INF;
    int dp(TreeNode *root){ 
   
        if(root->left == NULL && root->right == NULL){ 
   
            res = max(res,root->val);
            return root->val;
        }
        int l = 0,r = 0;
        if(root->left)l = max(l,dp(root->left));
        if(root->right)r = max(r,dp(root->right));
        res = max(res,l + r + root->val);
        return max(l,r) + root->val;
    }
    int maxPathSum(TreeNode* root) { 
   
        dp(root);
        return res;
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168676.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Linux 查看环境变量_linux修改环境变量顺序

    Linux 查看环境变量_linux修改环境变量顺序一、Linux的变量种类     按变量的生存周期来划分,Linux变量可分为两类:     1、永久的:需要修改配置文件,变量永久生效。     2、临时的:使用export命令声明即可,变量在关闭shell时失效。 二、设置变量的三种方法1、在/etc/profile文件中添加变量【对所有用户生效(永久的)】     用VI在文件/etc/profile文件

  • rsyslogd关闭_系统驱动丢失无法开机

    rsyslogd关闭_系统驱动丢失无法开机最近发现跑keepalived的几台机器的日志总是打印不完,还好给抛了一个报错,信息如下:[root@yw_lvs2_backupetc]#tail-n1000000/var/log/messages-20130526|grep”rate-limiting”May2011:43:55yw_lvs2_backuprsyslogd-2177:imuxsockbeginst…

  • vue双向数据绑定原理面试_vue双向绑定原理

    vue双向数据绑定原理面试_vue双向绑定原理vue.js则是采用数据劫持结合发布者-订阅者模式的方式,通过Object.defineProperty()来劫持各个属性的setter,getter,在数据变动时发布消息给订阅者,触发相应的监听回调。vue实现双向数据绑定的原理就是利用了Object.defineProperty()这个方法重新定义了对象获取属性值(get)和设置属性值(set…

    2022年10月18日
  • 彩色图和深度图转点云

    彩色图和深度图转点云环境:windows10、VS2013、opencv2.49、openNi、PCL1.8opencv环境搭建参考https://www.cnblogs.com/cuteshongshong/p/4057193.htmlhttps://blog.csdn.net/u013105549/article/details/50493069PCL1.8+openNi搭建参考https://blog.cs…

  • 破解Navicat提示生成激活码错误(注册激活)2022.02.27

    (破解Navicat提示生成激活码错误)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

  • sql:常用:group by 多个字段「建议收藏」

    sql:常用:group by 多个字段「建议收藏」首先groupby的简单说明:  groupby一般和聚合函数一起使用才有意义,比如countsumavg等,使用groupby的两个要素:  (1)出现在select后面的字段要么是是聚合函数中的,要么就是groupby中的.  (2)要筛选结果可以先使用where再用groupby或者先用groupby再用having下面看下groupb…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号