image.png

要点：

1. 最大路径和可能出现在三种情况中：
   左子树
   右子树
   根节点与左右子树
2. 返回值，返回当前节点和左右分支中的一支的最大值
3. maxsum 存放的事

    int dfs(TreeNode* root, int& maxsum){
        if(!root) return 0;
        int l = dfs(root->left, maxsum); // l: left child的分支最大值,
        int r = dfs(root->right, maxsum); //r: right child 的分支最大值
        maxsum = max(l+r+root->val, maxsum); // 和当前最大值比较
        return root->val + max(l,r); //child的分支 + 节点最大值
    }
    int maxPathSum(TreeNode* root) {
        int maxsum = INT_MIN;
        dfs(root, maxsum);
        return maxsum;
    }