> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/2.binary-tree/94binary-tree-maximum-path-sum.md).

# 124.Binary Tree Maximum Path Sum (H)

## 1.Description(Medium)

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:

```
  1
 / \
2   3
```

return`6`.

## 2.Code

any to any

时间 O(b^(h+1)-1) 空间 O(h) 递归栈空间 对于二叉树b=2

首先我们分析一下对于指定某个节点为根时，最大的路径和有可能是哪些情况。

第一种是左子树的路径加上当前节点，

第二种是右子树的路径加上当前节点，

第三种是左右子树的路径加上当前节点（相当于一条横跨当前节点的路径），

第四种是只有自己的路径。

乍一看似乎以此为条件进行自下而上递归就行了，然而这四种情况只是用来计算以当前节点根的最大路径，

如果当前节点上面还有节点，那它的父节点是不能累加第三种情况的。所以我们要计算两个最大值，

一个是当前节点下最大路径和，

另一个是如果要连接父节点时最大的路径和。

我们用前者更新全局最大量，用后者返回递归值就行了。

注意最后返回的是currentSum.

```
public int maxSum=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root){
        helper(root);
        return maxSum;
    }
    public int helper(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=helper(root.left);
        int right=helper(root.right);
        //连接父节点的最大路径是一、二、四这三种情况的最大值
        int currentSum= Math.max(Math.max(left,right)+root.val,root.val);
        //当前节点的最大路径是一、二、三、四这四种情况的最大值
        int currentMax= Math.max(currentSum,left+right+root.val);
        //用当前最大来更新全局最大
        maxSum=Math.max(maxSum,currentMax);
        return currentSum;
    }
```

前文 [手把手刷二叉树总结篇](https://labuladong.github.io/article/?qno=104) 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要用到「分解问题」的思维。

这题需要巧用二叉树的后序遍历，可以先去做一下 [543. 二叉树的直径](https://leetcode.com/problems/diameter-of-binary-tree) 和 [366. 寻找二叉树的叶子节点](https://leetcode.com/problems/find-leaves-of-binary-tree)。

`oneSideMax` 函数和上述几道题中都用到的 `maxDepth` 函数非常类似，只不过 `maxDepth` 计算最大深度，`oneSideMax` 计算「单边」最大路径和：

![](https://labuladong.github.io/algo/images/%E7%9F%AD%E9%A2%98%E8%A7%A3/124.png)

然后在后序遍历的时候顺便计算题目要求的最大路径和。

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

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 计算单边路径和时顺便计算最大路径和
        oneSideMax(root);
        return res;
    }

    // 定义：计算从根节点 root 为起点的最大单边路径和
    int oneSideMax(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMaxSum = Math.max(0, oneSideMax(root.left));
        int rightMaxSum = Math.max(0, oneSideMax(root.right));
        // 后序遍历位置，顺便更新最大路径和
        int pathMaxSum = root.val + leftMaxSum + rightMaxSum;
        res = Math.max(res, pathMaxSum);
        // 实现函数定义，左右子树的最大单边路径和加上根节点的值
        // 就是从根节点 root 为起点的最大单边路径和
        return Math.max(leftMaxSum, rightMaxSum) + root.val;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/2.binary-tree/94binary-tree-maximum-path-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.