437. Path Sum III （二叉树求sum）

淡淡的烟草味﹌ 2023-07-25 06:23 21阅读 0赞

题目：您将获得一个二叉树，其中每个节点都包含一个整数值。  
查找总计为给定值的路径数。  
该路径无需从根或叶开始或结束，但必须向下（仅从父节点到子节点移动）。  
该树的节点数不超过1,000，并且值的范围是-1,000,000至1,000,000。

思路：  
**数字大小的范围来告知我们使用的数据的类型是int 还是long long**，找路径数。  
第一种思路：  
以每个节点为起始的node开始遍历剩下的部分树（前序遍历），每个节点做一次起始节点。O（n^2）时间复杂度；递归  
第二种思路：  
以一个unordered\_map 为容器存储到这个节点的和为key，value是这个sum出现的次数，先压入一个key：0 value：1（代表sum为target了，出现一次）。从root节点开始遍历，如果为空就返回，否则求出sum+当前，如果当前的sum-target为0那么他的value就是1.就用一个变量求出出现次数。然后设置这个map位的新值，然后获得res为当前的出现次数+之后的出现次数（进入递归—）因为计算过了将该出现次数-1，因为往上回去了。  
**注意**：unordered\_map 的初始value为0，再用过该节点后要将它出现的次数减一。实现还原。

1，代码：

int pathSum(TreeNode* root, int sum) { 
            if(!root) return 0;
            return sumUp(root, 0, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
        }
    private:
        int sumUp(TreeNode* root, int pre, int& sum){ 
            if(!root) return 0;
            int current = pre + root->val;
            return (current == sum) + sumUp(root->left, current, sum) + sumUp(root->right, current, sum);
        }

代码2：花费的time比较多。

int pathSum(TreeNode* root, int sum) { 
            if(root==nullptr)
                return 0;
            unordered_map<int ,int>  cnt={ { 0,1}};
            return findpath(root,0,sum,cnt);
            
        }
        
        int findpath(TreeNode* cur, int sum, int target, unordered_map<int ,int >cnt)
        { 
            if(cur==nullptr)
                return 0;
            sum+=cur->val;
             int numtocur= 0;
            if(cnt[sum-target]!=0)
             numtocur+=cnt[sum-target];
            else
                numtocur=0;
            cnt[sum]= cnt[sum]? (cnt[sum]+1):1;
            int res=numtocur+ findpath(cur->left, sum, target, cnt)+
                            findpath(cur->right, sum, target, cnt);
            cnt[sum]=cnt[sum]-1;
            return res;
        }