首页 > 试题广场 >

二叉树中的最大路径和

[编程题]二叉树中的最大路径和
  • 热度指数：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 ，节点上的值满足
要求：空间复杂度 ，时间复杂度
示例1

输入

{1,2,3}

输出

6
示例2

输入

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

输出

41

说明


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

输入

{-2,#,-3}

输出

-2

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

树 dfs
难度：
0条回答 28946浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二叉树中的最大路径和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号