> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/meta-2025/binary-tree-maximum-path-sumdfs.md).

# 124. 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
```

**Example 2:**

```
Input:
 [-10,9,20,null,null,15,7]

   -10
   / \
  9  
20
/  \
15   7
Output:
 42
```

分析

**无论任何情况， 必须要包含根节点！！！！** return  = root+max(left,right), result = root+left+right

1. **处理负值**：
   * 使用 `max(dfs(node.left), 0)` 确保不考虑负贡献
   * 这样能正确处理所有节点值为负的情况
2. **路径计算**：
   * `path_sum` 计算当前节点作为最高点的完整路径和
   * `res` 记录全局最大值
3. **返回值**：
   * 只能返回当前节点加上左或右子树的最大贡献值
   * 这样保证返回的是单边路径

```
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    ans = float("-inf")
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        self.dfs(root)
        return self.ans
    def dfs(self,root):
        if not root:
            return 0
        left = max(0,self.dfs(root.left))
        right = max(0,self.dfs(root.right))
        self.ans = max(self.ans,left+right+root.val)
        return max(0,left+root.val,right+root.val)
```