> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/divide-conquer/124.binary-tree-maximum-path-sum.md).

# 124.Binary-Tree-Maximum-Path-Sum

## 124. Binary Tree Maximum Path Sum

## 题目地址

<https://leetcode.com/problems/binary-tree-maximum-path-sum/>

## 题目描述

```
Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6
```

## 代码

### Approach #1 Recursion

**Complexity Analysis**

* Time complexity : O(*N*) where `N` is number of nodes, since we visit each node not more than 2 times.
* Space complexity :O(log(*N*)). We have to keep a recursion stack of the size of the tree height, which is O(log(*N*)) for the binary tree.

```java
class Solution {
    int max_sum = Integer.MIN_VALUE;

  public int maxPathSum(TreeNode root) {
    max_gain(root);
    return max_sum;
  }

  public int max_gain(TreeNode node) {
    if (node == null) return 0;

    int left_gain = Math.max(max_gain(node.left), 0);
    int right_gain = Math.max(max_gain(node.right), 0);
    // 1. the maximum value contianing the current node
    int price_newpath = node.val + left_gain + right_gain;
    // 2. compare the maximu vlaue
    max_sum = Math.max(max_sum, price_newpath);
    // 3. Return a single path through the current node
    return node.val + Math.max(left_gain, right_gain);     
  }
}
```