[Day 30] Leetcode 124. Binary Tree Maximum Path Sum (C++)

前言

终於~到了最後一天，就用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。应该是不会每天发文了，但还是会尽量养成留下一些纪录的习惯，遇到有趣的题目也上来纪录一下。
期许可以继续努力，拥有更多相关知识。
下个主题见啦～