我的提交
class Solution {
public int maxPathSum(TreeNode root) {
Result result = getMaxPath(root);
if (result.atLeastOne < 0) {
return result.atLeastOne;
}
return Math.max(Math.max(result.toRoot, result.maxChild), result.atLeastOne);
}
public Result getMaxPath(TreeNode root) {
if (root.left == null && root.right == null) {
int max = Math.max(root.val, 0);
return new Result(max, max, root.val);
}
Result left = new Result();
if (root.left != null) {
left = getMaxPath(root.left);
}
Result right = new Result();
if (root.right != null) {
right = getMaxPath(root.right);
}
int toRoot = Math.max(0, Math.max(left.toRoot, right.toRoot)) + root.val;
int maxChild = Math.max(left.maxChild, right.maxChild);
int maxWithRoot = root.val + left.toRoot + right.toRoot;
int maxAtLeast = root.val;
if (root.left != null) {
maxAtLeast = Math.max(left.atLeastOne, maxAtLeast);
}
if (root.right != null) {
maxAtLeast = Math.max(right.atLeastOne, maxAtLeast);
}
return new Result(toRoot, Math.max(toRoot, Math.max(maxChild, maxWithRoot)), maxAtLeast);
}
class Result {
int toRoot;
int maxChild;
int atLeastOne;
Result() {
}
Result(int a, int b, int c) {
toRoot = a;
maxChild = b;
atLeastOne = c;
}
}
}
首先,考虑到保存一个全局的最大路径,忘记了全局变量这个东西,蛋疼地加在了返回值中。这样,返回值除了左或右子树+root,又多了全局最大路径。
其次,没有处理好所有节点为负的情况,第一次提交时,节点全负时,我返回了0。然后不得已在返回值中又加了一个最大节点的字段,如果到最后最大节点为负,那么抛弃0答案。
官方题解
阅读了官方题解后,我意识到有全局变量,然后可以把节点全为负的情况融入最大路径字段。
于是,递归函数返回值可以是root为起点的路径了,再加一个全局最大路径变量。
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
getMaxWithRoot(root);
return maxSum;
}
public int getMaxWithRoot(TreeNode root) {
if (root == null) return 0;
int left = Math.max(getMaxWithRoot(root.left), 0);
int right = Math.max(getMaxWithRoot(root.right), 0);
maxSum = Math.max(maxSum, root.val + left + right);
return Math.max(left, right) + root.val;
}
}