原题地址（中等）

方法1—深度优先搜索

这题有一个大坑：那就是没说结点一定为正，所以不能通过 sum<0 来减枝，只能一条路径一条路径的搜索查看。
**
常规的深搜就可以解决，但是要多注意一些细节。

class Solution {
public:
    vector<int> v;
    vector<vector<int>> vv;
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return vv;
    }
    void dfs(TreeNode* root, int target) {
        if(!root)   return;
        v.push_back(root->val);
        target -= root->val;
        if(root && !root->left && !root->right && target == 0)
            vv.push_back(v);  
        dfs(root->left, target);
        dfs(root->right, target);
        v.pop_back();
    }
};

方法2—广度优先搜索

思路是用一个哈希表来存储每个结点的父节点。然后用广度优先找到符合条件的叶子结点，再通过查找哈希表就可以还原出路径。

class Solution {
public:
    vector<vector<int>> ret;
    unordered_map<TreeNode*, TreeNode*> parent;
    void getPath(TreeNode* node) {  // 还原路径
        vector<int> tmp;
        while (node) {
            tmp.push_back(node->val);
            node = parent[node];
        }
        reverse(tmp.begin(), tmp.end());
        ret.push_back(tmp);
    }
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if (root == nullptr) {
            return ret;
        }
        queue<TreeNode*> que_node;
        queue<int> que_sum;
        que_node.emplace(root);
        que_sum.emplace(0);
        while (!que_node.empty()) {
            TreeNode* node = que_node.front();
            que_node.pop();
            int rec = que_sum.front() + node->val;
            que_sum.pop();
            if (!node->left&& !node->right && rec == sum) {
                getPath(node);
            }
            if (node->left) {
                parent[node->left] = node;
                que_node.push(node->left);
                que_sum.push(rec);
            }
            if (node->right) {
                parent[node->right] = node;
                que_node.push(node->right);
                que_sum.push(rec);
            }
        }
        return ret;
    }
};