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
输出：[]提示：
- 树中节点总数在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
题解
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>> 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;
}
};bfs
来自官方，通过queue完成广度遍历，在遍历左右子树的时候，记录子树的根节点为当前节点，如果当前和满足条件再从叶子节点去回溯路径（因为记录了父母节点，所以逆向回溯之后需要翻转路径）。
查看代码
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;
}
};