友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
124. 二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
1
/ \
2 3
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
-10
/ \
9 20
/ \
15 7
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
-
树中节点数目范围是
[1, 3 * 104] -
-1000 <= Node.val <= 1000
思路分析
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2020-04-01 23:09
*/
private int result = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
suforder(root);
return result;
}
private int suforder(TreeNode root) {
if (Objects.isNull(root)) {
return 0;
}
int right = Math.max(0, suforder(root.right));
int left = Math.max(0, suforder(root.left));
result = Math.max(result, left + root.val + right);
return Math.max(left, right) + root.val;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-01 10:57:14
*/
int result = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return result;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
// 这里可以利用 Math.max(0, dfs(root.right)) 简化代码。
// 但是，不简化可以击败 100%，简化后如一刷解法，却只能击败 49.84%
int left = dfs(root.left);
int right = dfs(root.right);
// 对于左右子树，这里有如下几种组合
// 1. root.val (left 和 right 都是负数)
// 2. root.val + Math.max(left, right) (left 和 right 有一个是正数)
// 3. left + root.val + right (left 和 right 都是正数)
result = Math.max(result, Math.max(left + root.val + right,
Math.max(Math.max(left, right) + root.val, root.val)));
// 对于返回给父节点，这里有两种可能
// 1. root.val (left 和 right 都是负数)
// 2. root.val + Math.max(left, right) (left 和 right 有一个是正数)
// 如果 max 方法支持传递多个参数，可以简写为：Math.max(0, left, right) + root.val
return Math.max(root.val, Math.max(left, right) + root.val);
}