Idea: the search function takes in a node as a parameter, and returns the length of the path that comes from either its left or right child, which can further grow to the parent node. While always returning the partial path length to the upper layer, the length of the path that contains nodes from both its left and right subtrees are also calculated to be a potential candidate result.

```
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxPathSum(TreeNode root) {
this.max = Integer.MIN_VALUE;
search(root);
return max;
}
int search(TreeNode node) {
if (node == null) return 0;
int leftResult = search(node.left);
int rightResult = search(node.right);
int result = Math.max(Math.max(leftResult, rightResult) + node.val, node.val);
max = Math.max(Math.max(leftResult + rightResult + node.val, result), max);
return result;
}
private int max;
}
```