###### tags: `LeetCode` `Tree` `Recursion` `Hard`
# LeetCode #124 [Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)
### (Hard)
路徑 被定義為一條從樹中任意節點出發，沿父節點-子節點連接，達到任意節點的序列。同一個節點在一條路徑序列中 至多出現一次 。該路徑 至少包含一個 節點，且不一定經過根節點。

路徑和 是路徑中各節點值的總和。

給你一個二元樹的根節點 root ，返回其 最大路徑和

---
左右子樹的值取其值與0中較大者, 這樣即使左右子樹值皆為負的, 最差的結果也是不取左右子樹(根節點值+0, 結果與不取相同)。

要注意的是比較最大值時是左子樹值(可能為0)+右子樹值(可能為0)+根節點值與當前最大值比較, 但是回傳節點最大值時只能取節點值加上左右子樹中值較大者(因為規定一個節點只能經過一次)。

---

class Solution {
public:
    int maxSum=INT_MIN;
    int maxPathSum(TreeNode* root) {
        helper(root);
        return maxSum;
    }
    int helper(TreeNode* node){
        if(!node) return 0;
        if(!node->left&&!node->right){
            maxSum=max(maxSum, node->val);
            return node->val;
        }
        int leftMax=max(helper(node->left),0);
        int rightMax=max(helper(node->right),0);
        maxSum=max(maxSum, node->val+leftMax+rightMax);
        return node->val+max(leftMax,rightMax);
    }
};