leetcode 437. 路径总和 III

墨蓝 2023-05-31 02:35 11阅读 0赞

**思路：  
从该结点开始计算sum  
从该节点开始继承之前的sum  
重复很多枝，会从一个结点重复开始很多次，需要剪枝**

class Solution { 
    public:
        int cnt = 0;
        int sum1 = 0;
        int pathSum(TreeNode* root, int sum) { 
            this->sum1 = sum;
            findw( root,sum );
            return cnt;
        }
        void findw( TreeNode* root, int sum ){ 
            if( root == nullptr ){ 
                return ;
            }else if( sum-root->val == 0 && root->left == nullptr && root->right == nullptr){ 
                cnt ++;
                return ;
            }else if( sum-root->val == 0){ 
                cnt++;
    
            }
            if( root->left != nullptr ){ 
                    findw( root->left,sum - root->val );
                    findw( root->left,sum1 );
            }
            if( root->right != nullptr){ 
                findw( root->right,sum - root->val );
                findw( root->right,sum1 );
            }
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

**用两重递归，规定只从一个结点开始，定住开始的结点，避免重复**

--------------------

class Solution { 
    public:
        int cnt = 0;
        int sum1 = 0;
        int pathSum(TreeNode* root, int sum) { 
    
            if (root == nullptr) { 
                return 0;
            }
    
            return paths(root, sum)
                    + pathSum(root->left, sum)
                    + pathSum(root->right, sum);
        }
    
        int paths( TreeNode* root, int sum ){ 
            if (root == nullptr) { 
                return 0;
            }
    
            int res = 0;
            if (root->val == sum) { 
                res += 1;
            }
    
            res += paths(root->left, sum - root->val);
            res += paths(root->right, sum - root->val);
    
            return res;
        }
    };

![在这里插入图片描述][2019102123263360.png]

--------------------

**思路三**  
**参考**  
**[https://leetcode-cn.com/problems/path-sum-iii/solution/liang-chong-fang-fa-jian-dan-yi-dong-ban-ben-by-a3/][https_leetcode-cn.com_problems_path-sum-iii_solution_liang-chong-fang-fa-jian-dan-yi-dong-ban-ben-by-a3]**

class Solution { 
    public:
        int ssum = 0;
        int ret = 0;
        map<int,int>mp;
        int pathSum(TreeNode* root, int sum) { 
            ssum = sum;
            mp[0] = 1;
            findw( root,0 );
            return ret;
        }
    
        void findw(TreeNode* root,int cur){ 
            if(root!=nullptr){ 
                if( mp[ cur+root->val - ssum] >= 1 ){ 
                    ret += mp[ cur+root->val - ssum];
                }
                mp[cur+root->val] += 1;
                findw( root->left,cur+root->val );
                findw( root->right,cur+root->val );
                mp[cur+root->val] -= 1;
            }
        }
    };

![在这里插入图片描述][20191029191602506.png]

**空间耗费挺大的，可能是因为map**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20230531/f9f09bd632e14ad08f047b11b0f6994a.png
[2019102123263360.png]: /images/20230531/587b6323908f4e5187f7deb63888abdf.png
[https_leetcode-cn.com_problems_path-sum-iii_solution_liang-chong-fang-fa-jian-dan-yi-dong-ban-ben-by-a3]: https://leetcode-cn.com/problems/path-sum-iii/solution/liang-chong-fang-fa-jian-dan-yi-dong-ban-ben-by-a3/
[20191029191602506.png]: /images/20230531/cbfce7fc0aac4d9193444c64d8ade30e.png