我要招人

去企业版

首页 > 试题广场 >

二叉树中的最大路径和

[编程题]二叉树中的最大路径和

热度指数：77451 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。

注意:

1.同一个节点在一条二叉树路径里中最多出现一次

2.一条路径至少包含一个节点，且不一定经过根节点

给定一个二叉树的根节点root，请你计算它的最大路径和

例如：
给出以下的二叉树，

最优路径是:2=>1=>3，或者3=>1=>2，最大路径和=2+1+3=6

数据范围：节点数满足 $1 \le n \le 10^5$ ，节点上的值满足 $|val| \le 1000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3}

输出

示例2

输入

{-20,8,20,#,#,15,6}

输出

说明


其中一条最大路径为:15=>20=>6，路径和为15+20+6=41

示例3

输入

{-2,#,-3}

输出

-2

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Maokt

发表于 2021-07-06 17:28:30

精华题解算法思想一：递归解题思路：首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。具体而言，该函数的计算如下。空节点的最大贡献值等于 0 展开全文

Peterliang

发表于 2021-07-18 11:29:45

精华题解题意分析这个题目我们需要计算出一棵二叉树上面的所有的路径当中，找出路径的和最大的那个值。这个题目的难点就是中途可能会存在权值为负数的情况，还有权值为0的情况不好处理。这个题目还是有点意思的，我们可以用一个类似与树形DP的方法进行求解。前缀知识，树形DP，树形DP就是我们假设我们知道了一棵二展开全文

牛一霸

发表于 2021-07-04 10:12:19

精华题解题目：二叉树的最大路径和描述：给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。这个路径的开始节点和结束节点可以是二叉树中的任意节点。示例1：输入：{-2,1}，返回值：1。解法一：思路分析：在该题目中可以使用递归的方法去解决问题，设置最大值为max，即展开全文

堆栈哲学

发表于 2021-07-08 21:45:12

精华题解分析读题：题目难点在于正确理解题意一棵二叉树注意题目对路径的定义：开始和结束结点可以是任意的结点。路径要求唯一，不能重复任意给出一棵二叉树的两个结点，路径指的是：分别从这两个结点向上走，找到最近的公共祖先结点而形成的路径。只有这样的定义下，路径才是唯一确定的。考虑如展开全文

leaves0924

发表于 2021-07-17 16:57:27

精华题解题目描述给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。这个路径的开始节点和结束节点可以是二叉树中的任意节点。例如：给出以下的二叉树，返回的结果为6示例1输入：{-2,1}返回值：1 题目分析题目描述的路径可以从任意节点开始到任意节点结束，与之前必须要从根节点到叶子结点的路径不同，展开全文

胖胖不吹牛

发表于 2020-03-20 12:42:41

不知道是不是有的小伙伴一开始和我一样，题目都不是很理解。先上代码，后面我跟大家详细的分享一下我的思路。 class Solution { public int res = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) 展开全文

华科不平凡

发表于 2020-08-10 11:42:53

多么痛的领悟返回条件写错，调了半小时；初始值写错，调了半小时；递归函数名写错，调了半小时。。。🥱 class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ 展开全文

数据结构和算法

发表于 2021-08-03 14:21:39

这道题要求的最大路径和如果是从根节点开始到叶子节点就好办了，我们可以通过递归的方式，从下往上，舍去比较小的路径节点，保留比较大的节点。但这道题要求的最大路径和并不一定经过根节点，如果再使用上面的方式就行不通了，对于这道题我们可以分为4种情况来讨论 1，只要当前节点，舍弃子节点。比如下面结点2的左右展开全文

LifelongCode

发表于 2021-02-02 21:20:57

问题分解，求树的最大路径，递归树的节点有三种可能：最大路径经过该节点本身从左子树到右子树最大路径经过节点本身向父节点发展最大路径就是节点本身可以将左右边子树返回的满足情况2的最大路径和f(left)，f(right)，以及节点本身值val, 做一个组合，假设当前最大值是MAX： MAX 展开全文

BrianWu

发表于 2021-07-16 00:28:55

/*描述给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。这个路径的开始节点和结束节点可以是二叉树中的任意节点例如：给出以下的二叉树:{1,2,3}返回的结果为6Main idea:问题分解，求树的最大路径，递归树的节点有三种可能：最大路径经过该节点本身从左子树到右子树最大路径经过节点本展开全文