力扣題目鏈接
題目解讀：
二叉樹路徑的定義即從1.任意節點出發，到達任意節點；2.該路徑至少包含一個節點，且不一定經過跟節點；3.求所有可能路徑和的最大值。
也就是說路徑途徑一個節點只能選擇來去兩個方向

考慮一個二叉樹單元

1. 設計一個函數，它應該能為我們選擇左路徑還是右路徑，所以該函數應該把 a 傳入，然后遞歸調用 b 和 c ，計算 b + a 和 c + a，選擇較大的值作為返回值，然后拿到全局最大和。(這里我們很容易確定參數和返回值，并且能夠一探遞歸函數的單層遞歸邏輯)

2. 需要注意的是，整個路徑的最大路徑和不一定經過根節點，所以我們的答案并不是根節點的返回值。

3. 這里需要一個能夠記錄所有路徑和中最大值的全局變量，它即為全局最大和。只要我們拿到了剛才的較大路徑，應該把它更新到全局最大和中。（確定了一個重要的全局變量）

4. 最后就是選擇 左中右，我們在得到 b 和 c 的遞歸值后計算 b + a + c 的值，如果比“左”和“右”大，就把它更新到全局最大和中。

特別討論：我們如何處理負數？
我們既然求的事最大和，如果我們把負數囊括進去，對我們的最大和只會是負增益，所以我們應該盡可能舍棄負數，直接用一個 max(0, x)。
注意：1.但是我們的函數中無論是向上連接 b 和 c，a 作為必經之地都是不能舍棄的；2.并且要保證全局最大和的初始值為 INT_MIN。
關于以上兩點，我們必須談到，如果三個節點都是 -1，a 會舍棄掉 b 和 c，但是在返回最終結果時， a 自己是不能被舍棄的，也就是說此時的最大路徑和只有 a 自己，即-1。

此時我們可以陸續寫一點代碼出來了，首先定義我們的遞歸函數：

int traversal(TreeNode* cur, int& maxSum) {}

好了，此時我們寫我們的主函數：

    int maxPathSum(TreeNode* root) {int maxSum = INT_MIN;traversal(root, maxSum);return maxSum;}

---

最后開始我們的重頭戲，遞歸函數

剛才遞歸三部曲我們已經走完了第一步：確定函數參數和返回值

第二步：確定終止條件。
這里的終止條件還是比較簡單的，就是遇到空節點了返回零：

        if (cur == nullptr) return 0;

第三步：確定單層遍歷的邏輯。

還記得我們剛才的思路嗎？先去遞歸找到左右路徑選哪個？

        int leftSum = max(0, traversal(cur->left, maxSum));int rightSum = max(0, traversal(cur->right, maxSum));sum = node->val + max(leftSum, rightSum);

在這里我們不得不說，如果我們選擇左右其中的一個，也就說明我們仍然需要往上去遍歷，此時我們應該把這個 sum 作為遞歸函數的返回值返回回去。

        int leftSum = max(0, traversal(cur->left, maxSum));int rightSum = max(0, traversal(cur->right, maxSum));return cur->val + max(leftSum, rightSum);

好了，我們現在需要選擇 左-中-右，此時我們的路已經被選死了，也就是說我們現在應該去處理中間節點（根節點）邏輯。

        int nodeSum = cur->val + leftSum + rightSum;maxSum = max(nodeSum, maxSum);

所以遞歸函數總體的代碼是：

        if (cur == nullptr) return 0;int leftSum = max(0, traversal(cur->left, maxSum));int rightSum = max(0, traversal(cur->right, maxSum));int nodeSum = cur->val + leftSum + rightSum;maxSum = max(nodeSum, maxSum);return cur->val + max(leftSum, rightSum);

總體代碼

class Solution {
public:int traversal(TreeNode* cur, int& maxSum) {if (cur == nullptr) return 0;int leftSum = max(0, traversal(cur->left, maxSum));int rightSum = max(0, traversal(cur->right, maxSum));int nodeSum = cur->val + leftSum + rightSum;maxSum = max(nodeSum, maxSum);return cur->val + max(leftSum, rightSum);}int maxPathSum(TreeNode* root) {int maxSum = INT_MIN;traversal(root, maxSum);return maxSum;}
};