本文主要是介绍力扣每日一题113：路径总和||，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
中等
给你二叉树的根节点 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
面试中遇到过这道题?
1/5
是
否
通过次数
407.3K
提交次数
644.1K
通过率
63.2%
思路：
这个和第112题一样，只不过我们现在要返回所有满足条件的路径，而不是判断是否满足条件。和上一题一样的方法，只不过是在维护路径和的同时，记录路径。
方法一：深度优先搜索
class Solution {
public:void dfs(vector<vector<int>> &ans,vector<int> &path,TreeNode* root,int sum,int targetSum){if(!root) return;else if(!root->left&&!root->right){path.push_back(root->val);if(sum+root->val==targetSum)ans.push_back(path);}else{path.push_back(root->val);if(root->left){dfs(ans,path,root->left,sum+root->val,targetSum);path.pop_back();}if(root->right){dfs(ans,path,root->right,sum+root->val,targetSum);path.pop_back();}}}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {vector<int> path;vector<vector<int>> ans;dfs(ans,path,root,0,targetSum);return ans;}
};方法二：广度优先搜索
和判断是否存在路径和等于目标的方法一样，要多注意的点就是，为了方便记录路径，设置一个哈希表，记录每个非根节点的父亲节点。这样每次找到一条符合条件的路径，就从叶子节点开始往上找，记录路径。
下面是官解
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;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;}
};这篇关于力扣每日一题113：路径总和||的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
