领扣LintCode算法问题答案-94. 二叉树中的最大路径和
目录
94. 二叉树中的最大路径和描述样例 1：样例 2：
题解鸣谢
94. 二叉树中的最大路径和
描述
给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）
样例 1：
输入: 给定一棵树（只有一个节点）:
2
输出：2
样例 2：
输入: 给定一棵树：
1
/ \
2 3
输出: 6
题解
public class Solution {
public int maxPathSum(TreeNode root
) {
Pointer
<Integer> max
= new Pointer<>(Integer
.MIN_VALUE
);
maxPathSum(root
, max
);
return max
.getV();
}
private int maxPathSum(TreeNode root
, Pointer
<Integer> max
) {
if (root
== null
) {
return Integer
.MIN_VALUE
;
}
int v
= root
.val
;
int maxLeft
= maxPathSum(root
.left
, max
);
int maxRight
= maxPathSum(root
.right
, max
);
if (maxLeft
> 0
&& maxRight
> 0) {
if (v
+ maxLeft
+ maxRight
> max
.getV()) {
max
.setV(v
+ maxLeft
+ maxRight
);
}
v
+= Math
.max(maxLeft
, maxRight
);
} else if (maxLeft
> 0) {
v
+= maxLeft
;
} else if (maxRight
> 0) {
v
+= maxRight
;
}
if (v
> max
.getV()) {
max
.setV(v
);
}
return v
;
}
class Pointer<T> {
private T v
;
public Pointer(T v
) {
this.v
= v
;
}
public T
getV() {
return v
;
}
public void setV(T v
) {
this.v
= v
;
}
}
}
原题链接点这里
鸣谢
非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。 欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。
