437. 路径总和 III
- 题目
- 算法设计:深度优先搜索
题目
传送门:https://leetcode.cn/problems/path-sum-iii/
算法设计:深度优先搜索
枚举每个节点和TA的子节点,看能不能组成路径和。
class Solution {
public:
int ans=0;
int pathSum(TreeNode* root, int sum) {
if(root) {
dfs(root, sum); // 以当前节点为父节点,对下面的每个子节点进行枚举,看能不能形成路径和
pathSum(root->left, sum); // 以当前节点下面的左子节点为父节点尝试
pathSum(root->right, sum); // 以当前节点下面的右子节点为父节点尝试
}
return ans;
}
void dfs(TreeNode* root, long sum) { // 枚举当前父节点和TA子节点的值,看能不能组成路径和
if(!root) return;
if(root->val==sum) ans++; // 当前节点 == sum,答案+1
dfs(root->left, sum - root->val); // 遍历左子树,sum = sum - 当前节点值
dfs(root->right, sum - root->val); // 遍历右子树,sum = sum - 当前节点值
}
};
可优化一下,使用前缀和。
把二叉树看做是数组,利用前后序遍历来维护前缀和。
class Solution {
public:
unordered_map<long, int> map;
int count = 0;
void countPathSum(TreeNode* root, int target, long sum){
if(!root)
return;
sum += root->val;
if(sum == target)
count++;
if(map.find(sum - target) != map.end())
// 检查从根到当前节点的路径中是否存在目标和路径
count += map[sum - target];
map[sum]++;
countPathSum(root->left, target, sum);
countPathSum(root->right, target, sum);
map[sum]--;
}
int pathSum(TreeNode* root, int targetSum) {
countPathSum(root, targetSum, 0);
return count;
}
};