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

# Maximum Path Sum Binary Tree II

1**.Links：**

牛客: <https://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a?tpId=196&tqId=37050&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-total%2Fquestion-ranking&tab=answerKey>

Laicode: <https://app.laicode.io/app/problem/139>

**2. 题目：**

Given a binary tree in which each node contains an integer number. Find the maximum possible sum **from any node to any node (the start node and the end node can be the same).**&#x20;

**Assumptions**

* ​The root of the given binary tree is not null

**Examples**

```
    -1
  /    \
2      11
     /    \
    6    -14
```

&#x20;

one example of paths could be -14 -> 11 -> -1 -> 2

another example could be the node 11 itself

The maximum path sum in the above binary tree is 6 + 11 + (-1) + 2 = 18

**How is the binary tree represented?**

We use the level order traversal sequence with a special symbol "#" denoting the null node.

**For Example:**

The sequence \[1, 2, 3, #, #, 4] represents the following binary tree:

```
    1
  /   \
 2     3
      /
    4
```

&#x20;&#x20;

**3想法**：

1. 和之前的任意两个leaf node的最大路径不同的是，这个是任意两个node之间的最大路径，所以在把一个node的left， right subtree的max path相加之前，要先看一下来自left， right 的max path是否大于0。 如果是left/right 的从上往下的max path sum <0, 那么就不用加那个path了
2. **思路：任意另个node的max path sum = max (left 的path sum， right的max path sum， left + right + node的跨了两个branchd的path sum)**    对于每一个node，找到它left， right subtree的自上而下的consecutive max path sum，如果这个从上往下的path sum是等于0，就加到cur.value 否则如果是负数时，负数加上去不会对max path sum有贡献所以直接设置为0，不考虑。之后在和global max对比更新。最后把加上当前的node的value的从上往下的consecutive的max path sum返回到上一层。
3. 步骤就是
   1. 遍历每一个node
   2. recursion的输入是node， 输出是从那个node开始自上往下最大的path sum
   3. 如果node是none，返回 0
   4. 在每一个node里面找到left, right children的自上往下的max path sum，如果自上往下max path sum >0, 就 left +right +node.val 得到从左往右的max path sum
   5. 把从左往右的max path sum和 global max path sum 对比并更新
   6. 返回加上当前节点的自上往下的max path sum

Source Code

```
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
  def maxPathSum(self, root):
    """
    input: TreeNode root
    return: int
    """
    # write your solution here
    # 1. question: input: root, output: maximum path sum from any node to any node
    # 2. idea:
    #   iterate every node in tree:
    #     for every node, find the max sum of its left consecutive path and max sum of its right consecutive path 
    #     compare the value of :  left path max sum, right path max sum, node.val and 
    #                            (left path max sum + right path max sum + node.val) and global max sum of path
    #    update global max sum of path of any two node， 更新任意两个node 之间的pathsum的最大值
    #    return max path sum of single path under this node 返回单条从上往下连续path的sum
    # Time: O(n), Space O(n) for imbalance tree, O(logn) for balance tree
    if not root:
      return None
    self.max_sum = -float('inf')
    self.helper(root)
    return self.max_sum
  def helper(self, node):
    if not node:
      return 0
    left = max(self.helper(node.left),0)
    right = max(self.helper(node.right),0)
    # if left or right <0, then no need to add them to max_path
    #  max_path can be single path or sum of two paths or only node.val
    # then compare it with the global max
    max_path = left + right + node.val
    self.max_sum = max(max_path, self.max_sum)
    # return the single path with max sum
    return max(left,right) +node.val


```

&#x20;