第七十三天 --- 力扣437（前缀和解法）

• 题目一（前缀和解法）
• • 思路
  • 代码

题目一（前缀和解法）

力扣:437

思路

1、上一次我们用的暴力O(n^2)的解法（详见：暴力解437 ），根据题目，我们发现，任意一个节点都可能是路径的起点，所以为了找全，我们就需要遍历每一个节点，在此之上研究他的子树问题，这种就是每找一次，起点终点都是确定的，所以为了不缺答案，要先枚举所有起点，再找对应的终点，所以复杂度O(n^2)
2、但是太复杂了，做了很多额外劳动，所以再读题，他让我们找一个路径，这个路径的和得符合要求，所以经典路径（区间)和的问题，用前缀和解法。
3、节点a和节点b处前缀和已知(分别是prefix_a,prefix_b)，如果从a到b的路径是答案，那么prefix_b-prefix_a=targetSum。
4、因为采用前缀和，所以开始遍历的时候，从上到下就是一个求取前缀和的过程，一旦一条路径走到了最下面，便开始向上回溯（回溯的值就是有多少个目标路径），每次回溯到一个节点，问左右儿子，他们统计到了多少，最后看以自己作为终点，有多少个对应的起点就有多少个答案路径，把三者做和即为这个节点能贡献的路径数。这里多说一下为啥这种算法快，因为当统计以自己为结束位置时，他想上只需要知道有多少个符合条件的前缀和，不需要知道哪些点的具体位置，只统计个数的话就很简单了，单独记录一下就行。

代码

注意：
1、一维前缀和，初始化的时候就是长度为0的时候！！！！！！！！
2、在开始继续向下统计的时候，当前节点前缀和算完了，要加入map里面，当左右儿子都完事了，当前节点利用价值没了，已经用过了，所以map里面对应项–即可。

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

（所有代码均已在力扣上运行无误）

经测试，该代码运行情况是(经过多次测试所得最短时间)：

时间复杂度O(N)
空间复杂度O(N)