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

这题首先需要遍历一遍树，把当前遍历的节点作为根节点出发，再去求符合条件的路径的个数。 第一次遍历可以用简单的层次遍历，利用队列实现；第二次遍历可以用dfs

方法一：非递归的dfs

/**
 * 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 FindPath(TreeNode* root, int sum) {
        // write code here
        if(!root)
            return 0;
        queue<TreeNode*> q;
        int count = 0;
        q.push(root);
        while(!q.empty()){//根节点层次遍历
            TreeNode* r =  q.front();
            count += dfs(r, sum);
            if(r->left)
                q.push(r->left);
            if(r->right)
                q.push(r->right);
            q.pop();
        }
        return count;
    }
    
    int dfs(TreeNode* root, int sum){//返回当前root下满足要求的路径个数
        if(!root)
            return 0;
        int count = 0;
        vector<TreeNode*> s;
        TreeNode* r = root,* pre = NULL;
        while(r || !s.empty()){//后序遍历
            while(r){
                s.push_back(r);
                r = r->left;
            }
            r = s.back();
            if(r->right && r->right != pre)
                r = r->right;
            else{
                if(isTrue(s, sum))
                    count ++;
                pre = r;
                r = NULL;
                s.pop_back();
            }
        }
        return count;
    }
    
    bool isTrue(vector<TreeNode*> s, int sum){
        for(int i = 0; i < s.size(); i ++)
            sum -= s[i]->val;
        if(!sum)
            return true;
        return false;
    }
};

方法二：递归的dfs

注意：当找到一条路径时，若路径尾节点非叶节点，则还需继续拓展路径，因为可能出现节点值为0、两条路径的拼接等情况。

/**
 * 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 FindPath(TreeNode* root, int sum) {
        // write code here
        if(!root)
            return 0;
        queue<TreeNode*> q;
        int count = 0;
        q.push(root);
        while(!q.empty()){//根节点层次遍历
            TreeNode* r =  q.front();
            count += dfs(r, sum);
            if(r->left)
                q.push(r->left);
            if(r->right)
                q.push(r->right);
            q.pop();
        }
        return count;
    }
    
    int dfs(TreeNode* root, int sum){//返回当前root下满足要求的路径个数
        if(!root)
            return 0;
        if(root->val == sum)
            return 1 + dfs(root->left, 0) + dfs(root->right, 0);
        return dfs(root->left, sum - root->val) + dfs(root->right, sum - root->val);
    }
};