113题

方法一：深度遍历（DFS）—自身对深度遍历还有认识不足需要进一步加强
首先通过遍历得到是否存在叶节点的路径长度等于所给的目标长度，在前序遍历中我们将所经历的节点都记录到path中，若最后的路径长度等于目标路径长度则将path压入结果，最后（也是自己没有想到的一部分）通过后序遍历将前序遍历所等到的path进行依次弹出，尝试压入新的路径节点，重复上述操作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root,targetSum);
        return result;
    }
    void dfs(TreeNode* root, int targetSum){
        if(root==NULL){
            return;
        }
        path.emplace_back(root->val);
        if(!root->left&&!root->right&&root->val==targetSum){
            result.emplace_back(path);
        }
        dfs(root->left,targetSum-root->val);
        dfs(root->right,targetSum-root->val);
        path.pop_back();
    }
    vector<int>path;
    vector<vector<int>>result;
};

方法2：使用unordered_map哈希表记录每个节点的父节点，使用反转函数reverse（）

class Solution {
public:
    vector<vector<int>>result;
    unordered_map<TreeNode*,TreeNode*>parent;
    void getpath(TreeNode* root){
        vector<int>temp;
        while(root!=NULL){
            temp.emplace_back(root->val);
            root=parent[root];
        }
        reverse(temp.begin(),temp.end());
        result.emplace_back(temp);
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root==NULL){
            return result;
        }
        queue<TreeNode*>s;
        queue<int>v;
        v.emplace(root->val);
        s.emplace(root);
        while(!s.empty()){
            TreeNode* head=s.front();
            s.pop();
            int temp=v.front();
            v.pop();
            if(head->left!=NULL){
                s.emplace(head->left);
                v.emplace(temp+head->left->val);
                parent[head->left]=head;
            }
            if(head->right!=NULL){
                s.emplace(head->right);
                v.emplace(temp+head->right->val);
                parent[head->right]=head;
            }
            if(head->right==NULL&&head->left==NULL&&temp==targetSum){
                getpath(head);
            }
        }
        return result;
    }
};