路径总和 III

问题

路径总和 III 原题链接：https://leetcode.cn/problems/path-sum-iii?envType=study-plan-v2&envId=top-100-liked

解法

第一种方法就是直接暴力，整体思路就是对树中所有节点遍历一遍（先序、中序、后序、层次遍历等都行），挨个深搜。时间复杂度为O(N^2)，其中 N 为该二叉树节点的个数。代码如下：

class Solution {
public:
    //最暴力的算法就是把所有节点都深搜一边
    int ans=0;
    void dfs(TreeNode* root,long long targetSum){
        if(!root) return;
        long long temp=targetSum-root->val;//卡极端数值有点没活硬整的意味
        if(temp==0){
            ans++;
            //return; 去掉这个return，因为他的子节点可以是0这样也符合条件
        }
        if(root->left!=nullptr) dfs(root->left,temp);
        if(root->right!=nullptr) dfs(root->right,temp);
    }
    int pathSum(TreeNode* root, int targetSum) {
        if(!root) return 0;
        stack<TreeNode*> stk;
        stk.push(root);
        TreeNode* node=root;
        //先序遍历
        while(!node || !stk.empty()){
            while(node){
                dfs(node,targetSum);//访问他
                stk.push(node->right);
                node=node->left;
            }
            node=stk.top();stk.pop();
        }
        return ans;
    }
};

第二种方法运用前缀和优化，通过在探索一条路（从根到叶）时记录他的前缀和避免了多次访问一个节点，将时间复杂度从O(N^2)优化到O(N)，其中 N 为该二叉树节点的个数。代码如下：

class Solution {
public:
    unordered_map<long long,int> mp;//存储前缀和及对应的个数
    int dfs(TreeNode* root,long long cur,int targetSum){
        if(!root) return 0;

        int ret=0;//存储当前节点能贡献的符合条件的路径数
        cur+=root->val;//累加当前节点值，更新前缀和

        //统计有多少个祖先节点的前缀和=curr-targetSum.这些祖先节点到当前节点的路径和就是targetSum
        if(mp.count(cur-targetSum)) ret=mp[cur-targetSum];
        mp[cur]++;//添加，子节点要用

        ret+=dfs(root->left,cur,targetSum);
        ret+=dfs(root->right,cur,targetSum);
        mp[cur]--;//递归时去除，别影响非你的子节点

        return ret;
    }
    int pathSum(TreeNode* root, int targetSum) {
        //初始化：前缀和为0的情况出现1次（处理「从根节点开始的路径」）
        //例：curr=8，targetSum=8 → curr-targetSum=0，prefix[0]=1 → ret=1，对应根到当前节点的路径和为8
        mp[0]=1;
        return dfs(root,0,targetSum);
    }
};