当前位置：首页 > news >正文

【每日一题】路径总和 III

news 来源：原创 2024/5/9 15:52:30

文章目录

题目描述
题解
- 解法一
- 解法二

在这里插入图片描述

题目描述

437. 路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：
在这里插入图片描述

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
在这里插入图片描述

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
在这里插入图片描述

题解

解法一

从每一个节点往下找，直到到叶子节点，记录count，其实这样会出现大量的重复计算，但是也能跑过。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int _sum;
    int path = 0;
    int INF = -0x3f3f3f3f;
//思路一：将当前头部作为跟进行计算,到叶子才停止，因为叶子节点可能是负值
    void GetSum(TreeNode* root,int cursum)
    {    
        if(root == nullptr) return;
        if(cursum < INF)//爆int
        return ;

        int tmp = cursum - root->val;
        if(tmp == 0)
        {
            path ++;//到0也继续往下找
            // if(root)
            // cout << root->val << endl;
        }
        GetSum(root->left, tmp);
        GetSum(root->right, tmp);
    }
    void PreOrder(TreeNode* root)
    {
        if(root == nullptr) return ;
        GetSum(root,_sum);
        PreOrder(root->left);
        PreOrder(root->right);
    }
    int pathSum(TreeNode* root, int targetSum) {
        _sum = targetSum;
        PreOrder(root);

        return path;
    }
};

解法二

由于解法一没有利用到前缀和 + 哈希表，所以出现了大量重复的计算。
解法二通过计算前缀和，维护当前的数组和，然后就可以从哈希表获得需要的连续路经总和。

但是需要注意，当该元素遍历完，需要把这个子路径的和从哈希表-1，因为后面遍历的节点看不到这个更新。
unordered_map<int,int> um= {{0,1}}是由于需要当遍历到当前元素刚好满足targetSum，此时需要的前缀是0，所以我们手动加上一个上去。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int> um= {{0,1}};//前缀和
    int pre = 0;
    int count = 0;
    int INF = 1e9;
    int pathSum(TreeNode* root, int targetSum) {
        if(!root) return 0;
        if(pre > INF) return 0;
        pre += root->val;
        auto it = um.find(pre - targetSum);
        if(it != um.end()) //找到了，就可以累计count 
        count += it->second;
        um[pre] ++ ;//维护当前的数组和
        //cout << pre << " " << um[pre] << " " << count   << endl;
        pathSum(root->left,targetSum);
        pathSum(root->right,targetSum);
        if(um.count(pre)) um[pre] --;//维护前缀和
        pre -= root->val;


        return count;
    }
};