124. Binary Tree Maximum Path Sum - 二叉树中的最大路径和

1 描述

给定一个非空二叉树,返回其最大路径和。

路径 : 一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

用例


输入: [1,2,3]

       1
      / \
     2   3

输出: 6
输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

解析

通过 &max 来记录全局最大值,通过返回ret来记录递归返回的值

二叉树 abc,a 是根结点(递归中的 root),bc 是左右子结点(代表其递归后的最优解)。
最大的路径,可能的只有三种路径情况:

    a
   / \
  b   c
  1. b + a + c。
  2. b + a + a父
  3. a + c + a父

其中情况 1,表示如果不联络父结点的情况,或本身是根结点的情况。
这种情况是没法递归的,但是结果有可能是全局最大路径和。
情况 2 和 3,递归时计算 a+b 和 a+c,选择一个更优的方案返回,也就是上面说的递归后的最优解啦。
另外结点有可能是负值,最大和肯定就要想办法舍弃负值(max(0, x))(max(0,x))。

但是上面 3 种情况,无论哪种,a 作为联络点,都不能够舍弃。

暴力枚举法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int result = -2147483648;

int helper(struct TreeNode* root) {
    if (root == NULL) return 0; 
    int left = helper(root->left);
    int right = helper(root->right);
    int threeNodeSum = root->val + left + right;
    int twoNodeSum = root->val + max(left, right);
    int oneNodeSum = root->val;
    int ret = max(twoNodeSum, oneNodeSum);
    int currentMax = max(ret, threeNodeSum);
    result = max(currentMax, result);
    return ret;
}

int max(int a, int b) {
    return a > b ? a : b; 
}

int maxPathSum(struct TreeNode* root){
    result = -2147483648;
    int temp = helper(root);
    return result;
}

分析

#define max(a, b) ((a) > (b) ? (a) : (b))

int maxPath = INT_MIN;

int dfs(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }

    // 左子树的最大和
    int left = dfs(root->left);
    // 右子树的最大和
    int right = dfs(root->right);
    // 当前节点路径(不需要联系父结点,或本身就已经是根结点而无父节点)的最大值 VS 当前全局最大值
    maxPath = max(left + right + root->val, maxPath);
    // 需要联系父节点,因此只返回子树最大分支
    return max(0, max(left, right) + root->val);

}

int maxPathSum(struct TreeNode *root) {
    // 初始化为最小可能的整数
    maxPath = INT_MIN;
    // 深度优先遍历
    dfs(root);
    return maxPath;
}

本文由博客一文多发平台 OpenWrite 发布!
Image placeholder
moaomao
未设置
  78人点赞

没有讨论,发表一下自己的看法吧

推荐文章
算法题:三角形的最小路径和

题目来源于力扣 理论基础 动态规划 三角形的最小路径和题目描述 给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。说明:如果你可以只使用O(n)的额外空间(n为三角形的

调查:企业数字化转型中面临的最大挑战是什么?

数字化转型是将新兴的数字技术集成到企业的各个方面的过程。比如最近的云迁移,其中数据和业务流程由第三方提供商管理。因此,数字化转型被视为利用技术简化运营并保持竞争力的一种方式。但Couchbase周三发

IEEE官方禁止华为参与期刊审稿,当全球最大技术学术机构向政治弯腰

大数据文摘出品作者:魏子敏、宋欣仪5月29日,作为全球最大专业技术组织之一的IEEE(电气和电子工程师协会)被曝出,在发给会员的内部邮件中禁止华为员工作为旗下期刊杂志的编辑和审稿人。今天早晨,IEEE

LeetCode 112. 路径总和

描述给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。说明:叶子节点是指没有子节点的节点。注意点:必须联通到叶节点分析从根节点开始,每当遇到一个

简化企业组网 H3C S1224F以太网交换机评测

相信很多企业都有自己的无线组网,且企业业务和办公越来越依赖于无线网络。有一些企业认为,在BYOD时代,无线组网满足了大部分的办公需求,相比有线来讲更加便捷易用。但在网络的稳定性方面,有线网络有着更明显

PHP跌出前十,铁打的 Python 连续3年第一:IEEE Spectrum 2019编程语言排行榜出炉

Python势头不减,依旧第一,而且进一步拉开了与其他语言的差距。这一结果,来自IEEESpectrum2019年度编程语言排行榜。这已经是Python连续3年保持第一。在Python之下,第二交椅的

大神程序员,夜夜coding到天明?Python之父昼伏夜出,PHP创始人24小时都在线

栗子鱼羊 发自凹非寺转自量子位 |公众号QbitAI大神程序员,夜夜coding到天明?有位名叫IvanBessarabov(简称“伊万”)的好事者,刚刚统计了各路大佬的代码提交(gitcommit)

二叉堆的实现

二叉堆 说明 在阅读该文章的时候,最好手中有一只纸和笔能够画出二叉堆的结构,会更加容易理解。 二叉树的定义 二叉树是每个结点最多有两个子树的树结构。通常子树被称作左子树和右子树。 二叉堆的定义

The Annual Summary Of 2019

Timeisflying,itarrivesattheendofyearagain.ThisismyfirstyearworkinginPinDuoDuoincanditseemsIarriveint

Java 8 Stream Api 中的 peek 操作

1.前言 在Java8StreamAPI详细使用指南中讲述了Java8StreamAPI中map操作和flatMap操作的区别。然后有小伙伴告诉我peek操作也能实现元素的处理。但是你知道map和pe

蓦然回首,Java 已经 24 岁了!

01、真没想到,Java竟然24岁了(算是90后)!提起Java,印象最深刻的当然就是:classCmower{ publicstaticvoidmain(String[]args){  System

大力再出奇迹,1024 张TPU,65536 batch size,仅76分钟训练完BERT!

大数据文摘出品作者:AndyBERT作为目前工业界中训练最耗时的应用,计算量甚至远大于机器视觉中的ImageNet训练。在BERT原论文中,JacobDevlin也是用了16台云TPU(64个TPU芯

算法题:乘积最大子序列

题目来源于力扣 理论基础 动态规划 乘积最大子序列题目描述 给定一个整数数组nums,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。 示例示例1: 输入:[2,3,-2,4] 输出:

2019年8月数据库流行度排行:双星闪耀 MySQL 成月度最大赢家

炎炎夏日,DB-Engines的8月榜单已经发布,本月积分MySQL获得了最显著的增长,较上月增加了24分,Oracle获得了18分的增长,Oracle公司的两个王牌产品,闪耀8月。以下是前10名的榜

欧洲最大笔融资,骗过软银!印度AI公司被曝造假,自动开发背后是真人码农

大数据文摘编辑部出品AI融资有泡沫,这大家都知道。但是,这泡沫能有多大呢?一家名叫Engineer.ai的明星AI初创公司刚刚刷新了这一纪录。这家以ai作为域名的公司由两名印度创始人创建,号称可以通过

欧洲最大MySQL用户之一,Booking.com数据库构架探秘!

吴鑫Booking.com数据库工程师TeamLead2015年加入总部位于阿姆斯特丹的Booking.com数据团队,现任数据库工程师团队负责人,主要是负责Booking.com里MySQL相关的运

我们走访了900名微软员工,为你揭秘全球最大软件公司的代码评审机制

大数据文摘出品来源:michaelagreiler编译:倪倪、钱天培、毅航全球最大的软件公司之一微软拥有约140,000名员工,其中大约44%,即超过60,000名员工,是工程师。Office、Vis

亚马逊将公布超过最大会话和知识数据集,超400万字

4月1日,亚马逊宣布:他们计划向公众公开“TopicalChat”数据集,超410万单词21万句子的语料库将于2019年9月17日发布。该数据集是为参加AlexaPrizeSocialbotGrand

5G是一个数据通道,未来最大的产业是人工智能 | 任正非对话卡普兰

大数据文摘出品昨天下午,华为创始人任正非邀请两位人工智能领域的国际顶级专家参与“与任正非咖啡对话”。这已经不是任正非第一次举办这种与行业专家的对话,上一次是在6月17日在与《福布斯》著名撰稿人乔治·吉

行业目前最大容量,东芝16TB硬盘里藏了哪些技术?

强大的SSD似乎给硬盘(HDD)带来了“毁灭性”的打击,使其淡出存储舞台,但事实并非如此。这种冲击确实存在,不过更多在消费级硬盘市场。对于企业级的数据存储,可以说从现在到未来很长一段时间内,硬盘依旧会

史上规模最大的中文知识图谱以及估值两个亿的 AI 核心代码

——大声告诉我,怎样才能可以让你变得更强?——充钱——???——都什么玩意?还有啥子咧?——充更多钱执迷不悟,无可救药了。所以,正确答案应该是什么呢?答:是知识。反正,说这些就是为了切入「知识」这个话

全球数据泄露报告:内部威胁成数据安全最大风险!

一份最新报告显示,由现任和离职员工引起的内部威胁使公司容易遭受破坏,并使公司数据面临风险。Code42发布的《2019年全球数据泄露报告》还质疑,是否需要资助和部署正确的数据安全解决方案来阻止内部威胁

电商直播成2019最大风口:依然扶不起阿斗蘑菇街?

在已经过去的“双十一”狂欢购物节中,涌现出了很多效果惊人的新兴销售模式,推动今年11月1日到11日,全国网络零售额超过8700亿元人民币,同比增长了26.7%。其中电商直播表现尤其突出。阿里官方数据显

安防摄像头RTSP/Onvif协议网页无插件直播视频流媒体服务器EasyNVR之按需直播如何有效利用最大上行带宽

介绍一般情况下,直播默认的播放方式是非按需直播,但很多情况下,不少用户会选择按需直播。按需直播能够减少带宽流量和服务器性能占用,最优的提高服务器的使用效率。下面我们来系统介绍下EasyNVR中按需直播

查询滑动窗口最大值的这4种方法不错

课程推荐:Java开发工程师--学习猿地精品课程 这是一道比较基础的算法题,涉及到的数据结构也是我们之前讲过的,我这里先买一个关子。这道面试题最近半年在亚马逊的面试中出现过28次,在字节跳动中出现过7