题解 | #二叉树中和为某一值的路径(三)# 递归和层序遍历

/**
 * 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 recursion(TreeNode* node, int sum){
        if(node == nullptr) return;
        if(sum - node->val == 0){
            res++;
        }
        recursion(node->left, sum - node->val);
        recursion(node->right, sum - node->val);
    }
    int FindPath(TreeNode* root, int sum) {
        // write code here
        queue<TreeNode*> que;
        if(root == nullptr) return res;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            for(int i=0 ;i<n; i++){
                TreeNode *tmp = que.front();
                que.pop();
                if(tmp->left) que.push(tmp->left);
                if(tmp->right) que.push(tmp->right);
                recursion(tmp, sum);
            }
        }
        return res;
    }
};