二叉树中的最大路径和

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

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

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

注意:

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

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

给定一个二叉树，请你计算它的最大路径和
例如：
给出以下的二叉树，

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

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

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

输入描述:

第一行输入一个正整数 n 表示二叉树的节点数
第二行输入 n 个整数表示二叉树上第 i 个节点的值
第三行输入 n 个整数表示二叉树上第 i 个节点的父节点是第几个节点，（其中第一个节点是根节点，其父节点表示为第零个节点0）。

输出描述:

输出最大路径和

示例1

输入

3
1 2 3
0 1 1

输出

示例2

输入

5
-20 8 20 15 6
0 1 1 3 3

输出

说明


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

示例3

输入

2
-2 -3
0 1

输出

-2

算法知识视频讲解

DizhX

发表于 2022-02-12 18:39:56

解题思路这道题求的是二叉树任意两个结点的最大路径和，因此计算思路是从最下层的子结点往上计算，记录每个结点的最大路径长度，一路算到根结点。在记录每个结点的最大路径长度时，还要考虑该结点跟它的左右子结点是不是最终的最大路径。计算方法 1.每个结点d 展开全文

七夕先生

发表于 2022-02-12 08:33:34

这个题目和leetcode的124题一样，其中有题解，但是大多数用的都是递归的方式。在牛客，这个题目被归在了动态规划中，咱们这里就用动态规划的方式解决。思路动态规划首先是思考最优子结构性质，假设dpnodedp_{node}dpnode是指以node为开始节点的路径的最大和。那么 dpnod 展开全文

闪电利剑

发表于 2022-02-15 13:51:46

LeetCode 题解：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/ import java.io. 展开全文

赫he

发表于 2023-11-04 10:44:44

思路对于二叉树种任一节点k，如果k作为某个路径上的一个点，这个路径的方向分两个方向： 1）从节点k到k的父节点的方向。因为k的父节点dfs(par(k)))需要用到dfs(k)，需要返回这个方向上的值，需要从k的左右子树中选择大的(要和0比较，贪心)那个子树再加上val(k) 2）不到k的父节展开全文