> For the complete documentation index, see [llms.txt](https://mabuxi.gitbook.io/mabuxi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mabuxi.gitbook.io/mabuxi/leetcode-summary/tree/bottom-up.md).

# Bottom Up

## 经典题目

[*124 Binary Tree Maximum Path Sum* ](https://leetcode.com/problems/binary-tree-maximum-path-sum/description/)

This is a traditional bottom up solution.

At each node of the recursion tree, we return the maximum path sum of the "single" path to the parent node, i.e., max(root.val, root.val + left, root.val + right). In the meantime, update the global maximum.

```java
public int maxPathSum(TreeNode root) {
    int[] max = new int[] { Integer.MIN_VALUE };
    helper(root, max);
    return max[0];
}
private int helper(TreeNode root, int[] max) {
    if (root == null) return 0;
    int left = helper(root.left, max);
    int right = helper(root.right, max);
    left = left < 0 ? 0 : left;
    right = right < 0 ? 0 : right;
    max[0] = Math.max(max[0], root.val + left + right);
    return root.val + Math.max(left, right);
}
```