二叉树中和为某一值的路径(三)

C++ 解法, 执行用时: 3ms, 内存消耗: 512KB, 提交时间: 2022-05-29

class Solution {
public:
    unordered_map<int, int> mp; 
    int dfs(TreeNode* root, int sum, int temp){ 
        if(!root) 
            return 0;
        int res = 0;
        temp += root->val; 
        if(mp.find(temp - sum) != mp.end())  
            res += mp[temp - sum]; 
        mp[temp]++; 
        res += dfs(root->left, sum, temp) + dfs(root->right, sum, temp); 
        mp[temp]--; 
        return res;
    }
    int FindPath(TreeNode* root, int sum) {
        mp[0] = 1; 
        return dfs(root, sum, 0);
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 512KB, 提交时间: 2022-03-13

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
    //找到以root为根的路径
//     int dfs(TreeNode* root, int sum){
//         if(!root) return 0;
//         sum -= root->val;
//         int ret = 0;
//         if(sum == 0) ++ret;
//         return ret + dfs(root->left, sum) + dfs(root->right, sum);
//     }
    
    unordered_map<int, int> m;
    int dfs(TreeNode* root, int tar, int presum){
        if(!root) return 0;
        int count = 0;
        presum += root->val;
        if(m.find(presum - tar) != m.end()) count += m[presum-tar];
        ++m[presum];
        int l = dfs(root->left, tar, presum);
        int r = dfs(root->right, tar, presum);
        --m[presum];
        return count + l + r;
    } 
    public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    int FindPath(TreeNode* root, int sum) {
        // write code here
//         if(!root) return 0;
//         int count = dfs(root, sum);
//         return count + FindPath(root->left, sum) + FindPath(root->right, sum);
        m[0] = 1;
        return dfs(root, sum, 0);
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 512KB, 提交时间: 2022-01-03

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /*
    解法1：两次dfs
    
    具体做法：
    可以使用两次dfs解决，第一次dfs遍历二叉树每个结点，每个结点都作为一次根结点，
    第二次dfs遍历以每个结点为根的子树，查找该子树是否有路径和等于目标值的。
    
    复杂度分析：
    时间复杂度：O(n^2)，其中n为二叉树的结点数，两层dfs嵌套递归
    空间复杂度：O(n)，每层dfs最深递归栈都只有n
    */
    int FindPath1(TreeNode* root, int sum) { //dfs 以每个结点作为根查询路径
        if(root == NULL) //为空则返回
            return res;
        dfs(root, sum); //查询以某结点为根的路径数
        FindPath(root->left, sum); //以其子结点为新根
        FindPath(root->right, sum);
        return res;
    }
    
    /*
    解法2：一次dfs+哈希表 - 大佬解法
    
    具体做法：
    两次dfs有些浪费，可以一次dfs解决。
    在进入以某个结点为根的子树中，向其中添加到该节点为止的路径和进入哈希表中，
    相当于每次分支下都有前面各种路径和，相当于我只要查找哈希表就可以找到从中间截断的路径，
    而遍历完这个分枝后依次删除这个分枝在哈希表中记录的路径和，避免影响别的分支，
    只有公共分支的路径和才会一直记录在哈希表中。
    
    复杂度分析：
    时间复杂度：O(n)，其中n为二叉树的结点数，一次dfs
    空间复杂度：O(n)，哈希表大小及递归栈最大为n
    */
    int FindPath(TreeNode* root, int sum) {
        mp[0] = 1; //路径和为0的有1条
        return dfs(root, sum, 0);
    }
    
private:
    int res = 0; // 解法1
    unordered_map<int, int> mp; //记录路径和及条数 - 解法2
    
    // 解法1调用
    void dfs(TreeNode* root, int sum){ //dfs查询以某结点为根的路径数
        if(root == NULL) return;
        if(sum == root->val) //符合目标值
            res++;
        dfs(root->left, sum - root->val); //进入子节点继续找
        dfs(root->right, sum - root->val);
    }
    
    // 解法2调用
    int dfs(TreeNode* root, int sum, int last){ //last为到上一层为止的累加和
        if(root == NULL) //空结点直接返回
            return 0;
        int res = 0;
        int temp = root->val + last; //到目前结点为止的累加和
        if(mp.find(temp - sum) != mp.end())  //如果该累加和减去sum在哈希表中出现过，相当于减去前面的分支
            res += mp[temp - sum]; //加上有的路径数
        mp[temp]++; //增加该次路径和
        res += dfs(root->left, sum, temp); //进入子结点
        res += dfs(root->right, sum, temp);
        mp[temp]--; //回退该路径和，因为别的树枝不需要这边存的路径和
        return res;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 516KB, 提交时间: 2022-02-15

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    //无所谓任意节点，起始或者结束的节点，个人认为应该抓住和为0的关键
    unordered_map<int, int> map;
    int FindPath(TreeNode* root, int sum) {
        // write code here
        map[0]=1;
        return DfsPath(root, sum,0);
    }
    //判断到本节点的这次路径中，是否存在map同索引，相同表明从这个索引到
    int DfsPath(TreeNode* root, int sum,int last) {
        if(!root) return 0;
        int res=0;
        //先序遍历对本次节点的判断，也是对一条从起始到结束的路径的每一个节点的判断
        int temp=root->val+last;
        if(map.find(temp-sum)!=map.end())    res+=map[temp-sum];//存在则增加所
        map[temp]++;        //初始化和增加当前路径一个节点的map
        res+=DfsPath(root->left,sum,temp);
        res+=DfsPath(root->right,sum,temp);
        map[temp]--;//弹出本层节点，不再影响另一条路的
        return res;
    }
    
    //原来的回溯法的,返回所有从头节点到尾节点
//     vector<vector<int>> FindPath02(TreeNode* root, int sum) {
//         // write code here
//         vector<vector<int>> Res;
//         vector<int> pp;
        
//     }
    
};

C++ 解法, 执行用时: 3ms, 内存消耗: 516KB, 提交时间: 2022-01-24

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    
    void dfs(TreeNode* root, int sum, int cur_s){
        if(root == nullptr){
            return ;
        }
        int temp = root->val + cur_s;
        if(mapp.find(temp - sum) != mapp.end()){
            res+= mapp[temp-sum];
        }
        mapp[temp]++;
        dfs(root->left, sum, temp);
        dfs(root->right, sum, temp);
        mapp[temp]--;
    }
    int FindPath(TreeNode* root, int sum) {
        // write code here
        res = 0;
        mapp[0]=1;
        dfs(root, sum , 0);
        return res;
    }
private:
    unordered_map<int, int>mapp;
    int res;
};

详情