题目描述

给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。
这个路径的开始节点和结束节点可以是二叉树中的任意节点
例如：
给出以下的二叉树，
 
返回的结果为6
代码：

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int res;
    int maxPathSum(TreeNode* root) {
        // write code here
        res=INT_MIN;
        getmax(root);
        return res;
    }
    int getmax(TreeNode *root)
    {
        if(root==NULL)
            return 0;
        int left=max(0,getmax(root->left));
        int right=max(0,getmax(root->right));
        res=max(res,root->val+left+right);
        return max(root->val+left,root->val+right);
    }
};

getmax函数用于dfs，求出左右子树加根的最大值，因为只能走一条路径，所以只能左右选一条，如果左右子树都小于0，取0，即都不走。
res用于记录，如果以当前节点为跟，左右子树都走的话，是否比已经记录的路径的和大，是的话将其存在根里，也就解决了不知道以哪个节点作为根的问题。