力扣 113. 路径总和 II [dfs,bfs]

 /**
 * 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>> res;//记录所有路径
    vector<int> vcur;//记录当前路径
    void work(TreeNode* cur, int targetSum){//targetSum是当前剩余值
        vcur.emplace_back(cur->val);//放入当前节点
        if(cur->val==targetSum&&cur->left==NULL&&cur->right==NULL){//相等且是叶子节点
            res.emplace_back(vcur);
        }
        if(cur->left)
            work(cur->left,targetSum-cur->val);//targetSum更新，减去当前val
        if(cur->right)
            work(cur->right,targetSum-cur->val);
        vcur.pop_back();//当前路径达不到target就依次删除节点
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root==NULL)
            return res;
        vector<int> vcur;
        work(root,targetSum);
        return res;
    }
};

 class Solution {
public:
    vector<vector<int>> ret;
    unordered_map<TreeNode*, TreeNode*> parent;

    void getPath(TreeNode* node) {//从叶子节点回溯，获取路径
        vector<int> tmp;
        while (node != nullptr) {
            tmp.emplace_back(node->val);
            node = parent[node];
        }
        reverse(tmp.begin(), tmp.end());//要翻转得到根节点到叶子节点的路径
        ret.emplace_back(tmp);
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        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 == nullptr && node->right == nullptr) {//如果是叶子节点判断是否满足条件
                if (rec == targetSum) {//如果满足条件就获取路径
                    getPath(node);
                }
            } 
            else {//不是叶子节点就继续放入左右子树
                if (node->left != nullptr) {
                    parent[node->left] = node;//记录当前节点node的左子树的父母节点为node
                    que_node.emplace(node->left);
                    que_sum.emplace(rec);//记录当前和
                }
                if (node->right != nullptr) {
                    parent[node->right] = node;//同理
                    que_node.emplace(node->right);
                    que_sum.emplace(rec);
                }
            }
        }
        return ret;
    }
};