[数据结构与算法]LeetCode-113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

深度优先，深度优先，考虑节点为空情况和vector<int>每次需要拷贝一个路径分支。

因为每条路径不能重叠，所有每次递归的时候，需要拷贝一个vector<int>出来

#include<iostream>
#include<vector>
using namespace std;
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) {
        vector<int> tmp;
        dfs(tmp, root, targetSum, 0);
        return res;
    }

    /* 第一个参数不传引用，考虑已经算出一个路径的情况，叠加的值不正确 */
    void dfs(vector<int> path, TreeNode* root, int targetSum, int currentSum) {

        /* 特殊情况 */
        if (root == NULL) {
            return;
        }

        currentSum += root->val;
        path.push_back(root->val);

        if (root->left == NULL && root->right == NULL) {
            if (currentSum == targetSum) {
                res.push_back(path);
            }
            return;
        }

        if (root->left) {
            dfs(path, root->left, targetSum, currentSum);
        }

        if (root->right) {
            dfs(path, root->right, targetSum, currentSum);
        }

    }
private:
    vector<vector<int>> res;

};