题目描述

其实我不太懂这个题为什么是hard题，anyway, 会做就好了。

样例

我不太喜欢写这些没用的，大家直接看原题链接好了，谢谢。

算法1

(递归) $O(n)$

我自己在这里踩的坑就是，有些node的值是负数， 所以如果算出来有负数的left或者right的话，就不要把它加到result里面去了。

这个题目的总体思路就是： 每次走到一个node，看到更大的path sum就更新一下result，并且返回当前node的最大的单枝path sum到上一层调用的地方。

我这里说到单枝path sum是因为，我们算一个path sum的时候一般是由左边的一条路和右边的一条路构成的，当然如果算的某一条路小于等于0的话就不要它了。

时间复杂度分析：o(n)

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = root->val;
        help(root, res);
        return res;
    }
private:
    int help(TreeNode* root, int& res) {
        if (!root) {
            return 0;
        }
        int left = help(root->left, res);
        left = left > 0 ? left : 0;
        int right = help(root->right, res);
        right = right > 0 ? right : 0;
        res = max(res, left + right + root->val);
        return max(left, right) + root->val;
    }

};