本文共 839 字，大约阅读时间需要 2 分钟。

哎，又是一道主题难以发挥抱负的题目。说到底，写代码之前得先把问题用最简单的方法描述清楚，否则温习看了半天，脑袋还是空空的。

最开始的时候，我把问题搞砸了，试图把最大值和路径和糅合在一起考虑。幸好及时调整了思路，明白了每条路径的最大值由路径值加上路径和决定后，才渐渐找到了出路。这也印证了一个真理：遇到难题时，先把代码写到能运行的程度再继续，这样能及时发现错误，避免赔功勋罪。

以下是针对该问题的解决方案代码：

class Solution {
private:
    int res;
    
public:
    int getMax(TreeNode* node) {
        if (!node) return 0;
        int left = getMax(node->left);
        int right = getMax(node->right);
        int sum = max(node->val, left + node->val, right + node->val);
        if (sum > res) res = sum;
        if (left + right + node->val > res) res = left + right + node->val;
        return sum;
    }
    
    int maxPathSum(TreeNode* root) {
        res = INT_MIN;
        getMax(root);
        return res;
    }
};

这个解法施عمال了两个关键点：先获得每条路径的最大值，然后在所有路径中找到总路径和最大的那个。这样分开考虑，问题就迎刃而解了。

代码虽不长，但 reveals了一个重要道理——如果代码超过 50 行就说明思路有问题，及时改正才不虚 ).

转载地址：http://elgyk.baihongyu.com/