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

# Binary Tree Maximum Path Sum II

Given a binary tree, find the maximum path sum from root.

The path may end at any node in the tree and contain at least one node in it.

## Example

Given the below binary tree:

```
  1
 / \
2   3
```

return 4. (1->3)

## Solution

为什么需要与零比较，主要是如果左右子树的值是负数，那么直接舍去，不需要。

```
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        this.val = val
        this.left, this.right = None, None
"""
class Solution:
    """
    @param root the root of binary tree.
    @return an integer
    """
    def maxPathSum2(self, root):
        # Write your code here
        if root is None:
            return 0

        left = self.maxPathSum2(root.left)
        right = self.maxPathSum2(root.right)

        return max(left, right, 0) + root.val #包含一个点就是括号外，不包含就是括号里面
```