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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    
    int res = 0;
    unordered_map<int, int> mp;//key为curSum值，value为这个值对应的路径条数（在经过当前节点的路径中的条数）
    void dfs(TreeNode* node, int sum, int curSum){
        if(!node) return;
        //此点和之前的任意个连续节点连起来是否是sum
        curSum += node->val;
        //不能留到子树给它算只有它一个怎么办，因为可能绝后
        //找到为0也没关系，加上去res不会增加，有一个条件语句主要是避免造出没有的mp来？（不是默认为0吗？）
        res += mp[curSum-sum];
        
        ++mp[curSum];//放在res += mp[curSum-sum];后面加，因为curSum相当于这个节点和下个节点交界处，
       // 若提前把它放入，会得到0（一个节点都没有的假路径），如果sum为0就会出现问题
        if(node->left)  dfs(node->left, sum, curSum);
        if(node->right) dfs(node->right, sum, curSum);
        --mp[curSum];
    }
    int FindPath(TreeNode* root, int sum) {
        // write code here
        //为了保证不会先出现后面的，应该用前序遍历
        if(!root) return 0;
       mp[0] = 1;//第一个间隙（第一个节点的头部空隙）
        dfs(root, sum, 0);
        return res;
    }
};

方法一：

往深处遍历，保证到该节点时是从双亲节点过来的，没有受到兄弟姐妹侄女侄儿等的影响，所以用前序遍历。

计算总和是在节点之间而不是节点上，所以mp[0]=1;保证从根节点到某节点这条路径也被计算在内。

相对官方解法没有条件语句判断是否存在一条路径满足要求，因为unordered_map<int, int>这样的结构初始化时会是int的默认值，在c++中int默认会是0（仅限于在容器中的情况，如果是直接int i; i会是任意值）。

空间复杂度和时间复杂度都是O(n)。

/**
 * 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整型
     */
    int res = 0;
    void dfs(TreeNode* Node, int sum) {
        if (!Node) return;
        //这个点是一定需要的，后面的节点不能跳着要，走这条路，这条路上的节点都需要
        if (sum == Node->val) ++res;
        dfs(Node->left, sum - Node->val);
        dfs(Node->right, sum - Node->val);
    }

    int FindPath(TreeNode* root, int sum) {
        // write code here
        if (!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* temp = q.front();
            q.pop();//为什么不能和上一句用逗号隔开?
            /*在C++中，`q.pop()` 是一个返回类型为 `void` 的函数，
            逗号运算符用于在一行中执行多个表达式，并且返回最后一个表达式的值。
            由于 `q.pop()` 没有返回值，不能与 `q.front()` 一起使用逗号运算符。*/
            dfs(temp, sum);
            if (temp->left) q.push(temp->left);
            if (temp->right) q.push(temp->right);
        }
        return res;
    }
};

方法二：

首先遍历每一个节点，然后以每一个节点为头节点，看包含这个节点往下走有没有和为sum的路径。

因为每一个节点都会作为头节点，且递归会从每一节点作为头节点递归完整该节点全部子树（路径），所以以任何一个节点开头的路径都会被找到而且找全。

它不作为头节点时，会不会被祖先节点连成一条可用路径是祖先节点那次递归要考虑的。

第一重遍历随便什么方法都行，只是要每个节点都作为头节点一次。

第二重遍历必须前序遍历，遵循双亲到子的顺序。

时间复杂度为O(n^2)。空间复杂度为O(n)。