题目的主要信息：

给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点

方法一：

采用递归。FindPath中用bfs计算以当前结点作为起点满足条件的路径个数，然后递归计算以当前结点的左孩子作为起点的满足条件的路径个数和以右孩子作为起点的满足条件的路径个数。用全局变量count来统计总的路径个数。bfs也是递归函数，如果root为NULL结束递归；否则用sum减去当前结点的值，如果sum变为0，说明这条以root结尾的路径和为sum，count加1.然后再往左右孩子递归。

具体做法：

class Solution {
public:
    int count = 0;//用来统计路径个数
    void bfs(TreeNode* root, int sum){
        if(!root) return ;
        sum -= root->val;//sum减去当前结点的值
        if(sum == 0){//如果sum等于0，表示该路径以root结尾的和为sum
            count++;
        }
        bfs(root->left,sum);//计算以当前结点的左孩子作为起点的满足条件的路径个数
        bfs(root->right,sum);//计算以当前的右孩子结点作为起点的满足条件的路径个数
    }
    
    int FindPath(TreeNode* root, int sum) {
        if(!root) return 0;
        bfs(root,sum);//计算以当前结点作为起点的满足条件的路径个数
        FindPath(root->left, sum);//计算以当前结点的左孩子作为起点的满足条件的路径个数
        FindPath(root->right, sum);//计算以当前结点的右孩子作为起点的满足条件的路径个数
        return count;
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，每个结点为起点遍历整颗树。
• 空间复杂度：$O(n)O(n)$，递归栈大小为n。

方法二：

采用队列。这一题的路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点。所以我们遍历二叉树的所有结点，以他们为起点找是否有和为sum的路径，用res统计所有符合条件的路径个数。遍历所有二叉树结点方法是用队列进行层次遍历，每遍历到一个结点，用dfs递归查找路径。 具体做法：

class Solution {
public:
    int res;
    void dfs(TreeNode* root,int sum,int path)
    {
        if(!root) return;
        path += root->val;//更新路径长度
        if(path == sum){
            ++res;
        }
        //往左递归
        dfs(root->left,sum,path);
        //往右递归
        dfs(root->right,sum,path);
    }
    
    int FindPath(TreeNode* root, int sum) {
        if(!root) return 0;
        queue<TreeNode*> q;//借助队列遍历所有结点
        //根节点入队
        q.push(root);
        int count = 0;//记录每层节点的个数
        res = 0;
        //path = 0;
        while(!q.empty()){//层次遍历所有结点，以每个结点为起始找路径
            //记录当前层数的节点
            count = q.size();
            while(count--){
                TreeNode *node = q.front();
                q.pop();
                //左右孩子入队
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
                dfs(node,sum,0);//找是否有符合条件的路径
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，每个结点为起点遍历整颗树。
• 空间复杂度：$O(n)O(n)$，递归栈大小为n。