437. 路径总和 III

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