题目链接：124. 二叉树中的最大路径和 - 力扣（LeetCode）

天美后台开发一面第三题，之前做过543. 二叉树的直径 - 力扣（LeetCode），解法基本一样，只不过累积的值变成了权重，还是用递归，不过我面试的时候没有考虑到负数的情况，有点遗憾，希望给个机会

class Solution {
public:
    int ans = INT32_MIN;

    int depth(TreeNode *root) {
        if (root == nullptr)
            return 0;
        int R = max(depth(root->right), 0);
        int L = max(depth(root->left), 0);
        ans = max(ans, R + L + root->val);
        return max(R, L) + root->val;
    }

    int maxPathSum(TreeNode *root) {
        depth(root);
        return ans;
    }
};