题目

binary-tree-maximum-path-sum

算法

* DFS

代码

class Solution {
public:
    int maxPathSum(TreeNode *root) {
        int res = root->val;
        maxPathSumDFS(root, res);
        return res;
    }
    int maxPathSumDFS(TreeNode *root, int &res) {
        if (!root) return 0;
        int left = maxPathSumDFS(root->left, res);
        int right = maxPathSumDFS(root->right, res);
        int top = root->val + (left > 0 ? left : 0) + (right > 0 ? right : 0);
        res = max(res, top);
        return max(left, right) > 0 ? max(left, right) + root->val : root->val; 
    }
};