前言

終於~到了最後一天，就用top 100 liked中還未完成的sum系列題目，最後的hard來畫上句點吧~ 這題是124. Binary Tree Maximum Path Sum，其實這個難度劃分有時候也不太準確，像這題就跟其他的medium差不多，甚至有些medium更難，所以也不要看到hard就被嚇到了XD

想法

這題其實拆解開來也是照著邏輯就寫完了。對於一個根節點而言，有幾種path組合─根節點、根節點+左子樹、根節點+右子樹、左子樹+根節點+右子樹。所以我們可以針對每個root，從最底下開始去計算包含該節點的最大值，然後往上比較，root+取左、root+取右、root取左取右；但往上考慮的時候不能考慮取左又取右的那個值，只能取其中一邊的，一直遍歷到根節點，最後取所有經過的最大值就行了。
整理一下邏輯如下：

• 從葉節點開始計算經過該點的可能最大值(該點以下的各種情形) maxValue某點 = max(該點,該點+maxRootSum左子樹,該點+maxRootSum右子樹,maxRootSum左子樹+該點+maxRootSum右子樹)
• 計算以該點作為葉節點可能的最大值(不可左右都考慮，這樣就不能往上連了) maxRootSum某點 = max(該點,該點+maxRootSum左子樹,該點+maxRootSum右子樹)

就可以寫出程式如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxRootSum(TreeNode* root, int& maxVal){
        if(nullptr==root){
            return 0;
        }
        else{
            int cur = root->val;
            int left = max(0, maxRootSum(root->left, maxVal));
            int right = max(0, maxRootSum(root->right, maxVal));
            maxVal = max(maxVal, cur+left+right);
            return cur+max(left, right);
        }
    }
    
    int maxPathSum(TreeNode* root) {
        // update the value from bottom
        int maxVal=root->val;
        maxRootSum(root, maxVal);
        return maxVal;
    }
};

程式中有做了一些簡化，例如前面的說的maxValue某點 = max(該點,該點+maxRootSum左子樹,該點+maxRootSum右子樹,maxRootSum左子樹+該點+maxRootSum右子樹)拆成了先考慮max(0, maxRootSum(root->left, maxVal));跟int right = max(0, maxRootSum(root->right, maxVal));，後面就只要比較max(maxVal, cur+left+right)，因為該點,該點+maxRootSum左子樹,該點+maxRootSum右子樹中的最大值會小於等於cur+left+right，因為他們不會小於0。

結語-完賽

這緊湊的一個月終於到了尾聲...但這才是我開始在軟體工程上努力的起點。
接下來會繼續天天刷題維持對於程式語法與邏輯的基本手感，但我對於軟體設計的相關知識實在太缺乏了，接下來會看一些軟體工程的相關書籍，期許自己更能掌握一些軟體設計該有的概念，例如設計模式、撰寫技巧等等，當然還有基礎的C++與OS。應該是不會每天發文了，但還是會盡量養成留下一些紀錄的習慣，遇到有趣的題目也上來紀錄一下。
期許可以繼續努力，擁有更多相關知識。
下個主題見啦～