113. 路径总和 II

思路：深度优先搜索dfs。细节看注释

/**
 * 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>> v;
    int copy_targetSum=0;
    void dfs(TreeNode * root,int sum,vector<int > &sta){
        if(root==nullptr) return;
        //把当前点加入到状态sta里
        sta.push_back(root->val);
        sum+=root->val;
        //当搜索到根节点时，判断此时路径上的和是否为目标值
        if(root->left==nullptr && root->right==nullptr){
            if(sum==copy_targetSum) v.push_back(sta);
        }
        
        if(root->left) dfs(root->left,sum,sta);
        if(root->right) dfs(root->right,sum,sta);
        sta.pop_back();//把当前点从状态里删除。
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        copy_targetSum=targetSum;
        vector<int > sta;
        dfs(root,0,sta);
        return v;
    }
};