|
给你二叉树的根节点 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;
};
|