I finished one following the similar idea in LC maxPathInTree. Use a wrapper
to return the current closeMax and farMax of each subTree. At the same time
, calculate the currentMaxPathSum:
public static int maxPath = Integer.MIN_VALUE;
public static int maxJumpPathinTree(TreeNode root) {
maxJumpPathHelper(root);
return maxPath;
}
public static SumWrapper maxJumpPathHelper(TreeNode root) {
if (root == null) return new SumWrapper(0, 0);
SumWrapper left = maxJumpPathHelper(root.left);
SumWrapper right = maxJumpPathHelper(root.right);
int valWithRoot = root.val;
if (left.far > 0) valWithRoot += left.far;
if (right.far > 0) valWithRoot += right.far;
int valWithoutRoot = Math.max(left.far, left.close);
if (Math.max(right.far, right.close) > 0) valWithoutRoot += Math.max
(right.far, right.close);
maxPath = Math.max(maxPath, Math.max(valWithRoot, valWithoutRoot));
int close = root.val;
if (Math.max(left.far, right.far) > 0) close += Math.max(left.far,
right.far);
int far = Math.max(Math.max(left.far, left.close), Math.max(right.
far, right.close));
return new SumWrapper(close, far);
}
class SumWrapper {
int close;
int far;
SumWrapper (int close, int far) {
this.close = close;
this.far = far;
}
}