力扣437 路径总和变式，我如何在遍历过程中返回所有路径

Question

力扣437

但是我的目的是返回符合条件的路径中和最小的那一条

我不知道应该如何在递归的过程中把路径记录下来

题目描述
小蓝鲸们得到了一串数字，这串数字可以唯一的表示一棵二叉树，其规则如下：

1.从这串数字的开始一直到最后，依次是水平顺序遍历二叉树的各个节点的值(值不为0)，若二叉树非空节点的某个子节点为空，则用0表示。
2.同时，二叉树的各个节点按照在这串数字中出现的顺序编号，(从0开始)。
例如[5,7,4,1,0,3,0][5,7,4,1,0,3,0]，对应如下的二叉树，每个节点括号内是节点值，括号外是节点编号。

       0(5) 
      /    \
    1(7)   2(4)
    /      /
  3(1)   4(3)

路径被定义为一条从任意节点出发，通过边的连接，到达任意节点的序列。同一个节点在一条路径序列中至多出现一次。一条路径至少包含一个节点，且不一定经过根节点。路径和是路径中各节点值的总和。

现在,给定这串数字的序列，小蓝鲸需要构建出这棵二叉树，并找到其中具有最大路径和，且长度最短的路径。

(题目数据保证符合条件的路径只有一条，输出时规定节点编号小的路径端点在前，如3->2->4和4->2->3代表相同的路径，只输出3->2->4)

输入格式
第一行输入一个整数：nn，表示数组的大小。

第二行输入 nn 个整数，为表示二叉树的数组。

输出格式
输出kk个整数，代表最短的最大和路径。

样例数据
样例1
输入

7
-10 9 20 0 0 15 7
输出

3 2 4
解释：二叉树形为

   0(-10)
   /    \
 1(9)   2(20)
       /    \     
      3(15)  4(7)

最大和为15+20+7=42，对应最大和路径只有一条，为3->2->4

样例2
输入

10
-5 2 3 1 0 -1 0 0 0 1
输出

2
解释：二叉树形为

   0(-5)
   /    \
 1(2)   2(3)
 /      /
3(1)  4(-1)
       /
    5(1)

最大和为3, 对应最大和路径有3条，分别为1->3，2和2->4->5，输出最短路径为2

数据规模与约定
1≤n≤6×1041≤n≤6×104

Node.val(节点值的范围) ∈[−1000,−1]⋃[1,1000]∈[−1000,−1]⋃[1,1000]
时间限制：1s1s
空间限制：128MB128MB

Answer 1

class Solution {
public:

    unordered_map<long long, int> item;//存储前缀和，key代表前缀和，value代表出现次数

    int treePrefixSum(TreeNode* root, int cur, int target) {
        if (root == nullptr) {
            return 0;
        }
        
        cur += root->val;//求前缀和
        int ans = 0;//答案
        //后根遍历回溯算法
        item[cur]++;//自己已经统计完了前缀和，要加入map
        ans += treePrefixSum(root->left, cur, target);//加入左右儿子统计结果
        ans += treePrefixSum(root->right, cur, target);
        item[cur]--;

        if (item.count(cur - target)) {//统计以当前节点为结束符的路径个数
            ans += item[cur - target];
        }

        return ans;//返回三者的和
    }

    int pathSum(TreeNode* root, int targetSum) {
        item[0] = 1;
        return treePrefixSum(root, 0, targetSum);
    }
};