[数据结构与算法]leetcode. 124 二叉树中的最大路径和（存储对应路径）

附带路径的参考解答

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    int ans = INT_MIN;
    vector<int> path;
public:
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return ans;
    }
    pair<int,vector<int>> maxGain(TreeNode* root){
        if(root == nullptr) return {0, {}};
        auto[left_sum, left_path] = maxGain(root->left);
        auto[right_sum, right_path] = maxGain(root->right);
        left_sum = max(0, left_sum);
        if(left_sum == 0) vector<int>().swap(left_path);
        right_sum = max(0, right_sum);
        if(right_sum == 0) vector<int>().swap(right_path);
        if(left_sum + right_sum + root->val > ans){
            ans = left_sum + right_sum + root->val;
            path.clear();
            path.insert(path.end(),left_path.begin(),left_path.end());
            path.push_back(root->val);
            path.insert(path.end(), right_path.begin(),right_path.end());
        }
        int res;vector<int> p;
        if(left_sum >0 && left_sum > right_sum){
           res = root->val + left_sum;
           p.insert(p.end(),left_path.begin(), left_path.end());
           p.push_back(root->val);
        }else if(right_sum > 0 && right_sum > left_sum){
            res = root->val + right_sum;
            p.push_back(root->val);
            p.insert(p.end(), right_path.begin(), right_path.end());
        }else{
            p.push_back(root->val);
            res = root->val;
        }
        return {res, p};
    }
};