剑指Offer_34_二叉树中和为某一值的路径

❗️LeetCode_113_路径总和2

题目描述：

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例：

给定如下二叉树，以及目标和 target = 22，
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回：
[
   [5,4,11,2],
   [5,8,4,5]
]

提示：节点总数 <= 10000

解法1：递归

/**
 * 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> path;  //定义一个容器

    vector<vector<int>> pathSum(TreeNode* root, int sum) {

        dfs(root, sum);

        return res;
    }

    //递归求解
    void dfs(TreeNode* curr, int target) {

        if (curr != nullptr) {

            target -= curr->val;
            path.push_back(curr->val);

            if (target != 0 || curr->left != nullptr || curr->right != nullptr) {

                dfs(curr->left, target);
                dfs(curr->right, target);
            } else {
                
                res.push_back(path);  //满足结果
            }
            
            //注意理解这个回溯❗️可以注释这行代码看看效果
            //当路径中有不对的值比如7、或者访问完左子树需要开始访问右子树，都需要回溯路径中的值
            path.pop_back();  
        }
    }
};