# Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

Example

Given the below binary tree:

```<code>  1
/ \
2   3
</code>```

return `6`.

```private class maxPathResult {
int maxSinglePath;
int maxPath;
public maxPathResult(int maxSinglePath, int maxPath) {
this.maxSinglePath = maxSinglePath;//start from root to any nodes
this.maxPath = maxPath;//max path in the tree
}
}
public int maxPathSum(TreeNode root) {
// write your code here
return helper(root).maxPath;
}

public maxPathResult helper(TreeNode root) {
if (root == null) {
return new maxPathResult(Integer.MIN_VALUE, Integer.MIN_VALUE);
}
maxPathResult left = helper(root.left);
maxPathResult right = helper(root.right);

int maxSinglePath = Math.max(left.maxSinglePath, right.maxSinglePath);
maxSinglePath = maxSinglePath < 0 ? root.val : root.val + maxSinglePath;

int maxDoublePath = 0;
if (left.maxSinglePath > 0) {
maxDoublePath += left.maxSinglePath;
}
if (right.maxSinglePath > 0) {
maxDoublePath += right.maxSinglePath;
}
maxDoublePath += root.val;

int maxPath = Math.max(Math.max(left.maxPath, right.maxPath), maxDoublePath);
return new maxPathResult(maxSinglePath, maxPath);
}```

1. 通过根的path.

(1)如果左子树从左树根到任何一个Node的path大于零，可以链到root上

(2)如果右子树从右树根到任何一个Node的path大于零，可以链到root上

2. 不通过根的path. 这个可以取左子树及右子树的path的最大值。

1. 本树的最大path。

2. 本树从根节点出发到任何一个节点的最大path.

Share