力扣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
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 还是 小蓝鲸们的那个题?