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

## Thoughts

二叉树上返回和最大的路径和。和diameter异曲同工。分治，global max记录全局最优, helper返回从下往上且包含当前节点的能继续往上延伸的最大sum。全局最优可能是同时包含左右两支。由于负数的存在，返回时node.val+max(l, r, 0)，表示局部最优是负数时最佳选择是不选子结点。

## Code

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.res = -float(inf)
    
    def dfs(self, node):
        if node == None:
            return 0
        l, r = self.dfs(node.left), self.dfs(node.right)
        self.res = max(self.res, node.val + max(l, 0) + max(r, 0))
        return node.val + max(0, max(l, r))
        
    def maxPathSum(self, root: TreeNode) -> int:
        self.dfs(root)
        return self.res
```

## Analysis

每个节点遍历一次, 时间复杂度O(N).

## Ver.2

用区分backtracking的Iterative写。 当pop()后, peek()得到的是pop的父节点.和分治一样直接利用pop()时对应的preRes. 如果还有右子树没处理, 则不pop父节点, 而同样处理右子树. 注意这时preRes需要清零, 因为preRes存的还是左子树的结果, 右子树肯定不能直接用到左子树的结果。

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        stack<TreeNode*> s;
        stack<int> mlens;
        TreeNode *pre;
        int plen = 0;
        const auto push_left = [&](TreeNode *cur) {
            while (cur != NULL) {
                s.push(cur);
                mlens.push(0);
                cur = cur->left;
            }
            pre = NULL;
            plen = 0;
        };
        push_left(root);
        while (!s.empty()) {
            const auto cur = s.top();
            auto &mlen = mlens.top();
            if (cur->right != pre) {
                // Handling left backtracking.
                mlen = plen;
                push_left(cur->right);
                continue;
            }
            // Handling right backtracking.
            int l = max(0, mlen);
            int r = max(0, plen);
            res = max(res, cur->val + l + r);
            plen = cur->val + max(l, r);
            pre = cur;
            s.pop();
            mlens.pop();
        }
        
        return res;
    }
};
```


---

# Agent Instructions: 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://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/divide-and-concquer/diameter-of-binary-tree/binary-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.