起点有 n 个，终点有 n 个，总的路径数量为 $n^2$ 个。必须要想一个办法把所有路径枚举出来，这里常用的一种枚举方法是 枚举路径的最高点 （最近公共祖先）

遍历的过程中，左右子树是独立的，分别取最大值就可以。

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return res;
    }
private:
    int res = INT_MIN;
    int dfs(TreeNode* root) {
        if (!root) return 0;
        int L = max(0, dfs(root->left));
        int R = max(0, dfs(root->right));
        res = max(res, L + R + root->val);
        return max(L, R) + root->val;
    }
}