题解 | #二叉树中的最大路径和#

class Solution {
public:
    /**
     * @param root TreeNode类
     * @return int整型
     */
    int res;
    int dfs(TreeNode* root,int CurrentSum){
        if (root == NULL) return CurrentSum;
        // 左侧直线
        // 右侧直线
        // 左侧直线+右侧直线-根节点值-2*currentsum
        int left = dfs(root->left, CurrentSum + root->val);
        int right = dfs(root->right, CurrentSum + root->val);
        int total=left+right-CurrentSum*2-root->val;
        int rv=max(left,right);
        res = max(max(total,rv),res);
        return rv;
    }
    int maxPathSum(TreeNode* root) {
        if(root==NULL) return 0;
        res=root->val;
        dfs(root,0);
        return res;
    }
};

这道题想明白了并不难，关键是对题目的理解：

如果问从根节点到叶节点的路径中，节点值求和最大值，直接进行dfs遍历即可，没当到达叶节点，则与保存的最大值进行比较，取最大值即可。dfs函数的设计可以是下面的形式：

void dfs(root,CurrentSum){
  // ……
}

这道题不一样，增加了从子节点到父节点的路径。但也要想明白，如果想启用从子节点到父节点的路径，则最后路径的结果一定是左子树最大结果+右子树最大结果+父节点的值。而父节点到它的父节点的路径就不能用了，因为同一个节点在一条二叉树路径中最多出现一次。

举个例子：

所以其实要比较的路径有两种，一种是倒 “V” 字形的路径，包含从子节点到父节点的路径。另外一种正常dfs时的路径。