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

力扣437

img


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

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

img


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

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


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);
    }
};

题目需要的是返回路径的index顺序,比如说3->4,1->2->3,我知道如何递归求值,但是不知道如何在递归的过程中,记录下所有满足要求的路径,用数组储存

递归路径记录是采用记录上一个点的访问,例如pre[i] = j,表述i从j转移过来的,即j->i

问下,是要求力扣437 还是 小蓝鲸们的那个题?