当路径到达某个节点时，该路径既可以前往它的左子树也可以前往它的右子树，但如果路径同时经过它的左右子树，那么就不能经过它的父节点。

由于需要先求出左右子树的路径节点值之和的最大值，再求根节点，所以要用后序遍历。

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        //因为节点值最小为-1000，即使二叉树中所有节点都是-1000
        //最大路径和就是其中一个节点，即-1000
        int maxSum = -1000;
        dfs(root, maxSum);

        return maxSum;
    }

    int dfs(TreeNode* root, int& maxSum)
    {
        if (root == nullptr) return 0;

        //若当前子树和小于0，则不选当前子树所在的路径，于是取0
        int left = max(0, dfs(root->left, maxSum));
        int right = max(0, dfs(root->right, maxSum));

        //路径同时经过当前节点左右子树的情况
        maxSum = max(maxSum, root->val + left + right);

        //函数的返回值是经过当前节点root并前往其左子树或右子树的路径的节点值之和的最大值
        return root->val + max(left, right);
    }
};