[LeetCode] 113. Path Sum II 路径和 II
LeetCode 路径 II path sum 113
2023-09-27 14:28:37 时间
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22
,
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
return
[ [5,4,11,2], [5,8,4,5] ]
112. Path Sum 的拓展,上一题只要求返回是否存在,这题要求输出具体的路径。
Java:
/** * 和原来的不一样,这题要完全遍历,使用track跟踪当前的进度,进入dfs时压进去,出dfs时推出,当时叶节点且和正好为0是,克隆添加到结果中。 * */ public class Solution { List<List<Integer>> list; LinkedList<Integer> track; public void dfs(TreeNode root,int sum){ if(root==null) return; sum-=root.val; track.add(root.val); if(sum==0 && root.left==null && root.right==null) list.add((LinkedList<Integer>)track.clone()); dfs(root.left,sum); dfs(root.right,sum); track.remove(track.size()-1); } public List<List<Integer>> pathSum(TreeNode root, int sum) { this.list=new ArrayList<List<Integer>>(); this.track=new LinkedList<Integer>(); dfs(root,sum); return this.list; } }
Python:
class Solution: # @param root, a tree node # @param sum, an integer # @return a list of lists of integers def pathSum(self, root, sum): return self.pathSumRecu([], [], root, sum) def pathSumRecu(self, result, cur, root, sum): if root is None: return result if root.left is None and root.right is None and root.val == sum: result.append(cur + [root.val]) return result cur.append(root.val) self.pathSumRecu(result, cur, root.left, sum - root.val) self.pathSumRecu(result, cur,root.right, sum - root.val) cur.pop() return result
C++:
class Solution { public: vector<vector<int> > pathSum(TreeNode *root, int sum) { vector<vector<int>> res; vector<int> out; helper(root, sum, out, res); return res; } void helper(TreeNode* node, int sum, vector<int>& out, vector<vector<int>>& res) { if (!node) return; out.push_back(node->val); if (sum == node->val && !node->left && !node->right) { res.push_back(out); } helper(node->left, sum - node->val, out, res); helper(node->right, sum - node->val, out, res); out.pop_back(); } };
类似题目:
[LeetCode] 437. Path Sum III 路径和 III
All LeetCode Questions List 题目汇总
相关文章
- 【LeetCode】不同路径 [M](数学)
- 【LeetCode】不同的子序列 [H](动态规划)
- 【LeetCode】最佳买卖股票时机含冷冻期 [M](动态规划)
- LeetCode第63题--不同路径
- leetcode 4 Median of Two Sorted Arrays
- LeetCode_BFS_DFS_简单_1971.寻找图中是否存在路径
- LeetCode_BFS_困难_864.获取所有钥匙的最短路径
- LeetCode_二叉树_前缀和_中等_437.路径总和 III
- LeetCode_图的遍历_中等_797. 所有可能的路径
- LeetCode_dijkstra算法_中等_1631. 最小体力消耗路径
- LeetCode_滑动窗口_困难_30.串联所有单词的子串
- LeetCode_二叉树_简单_112.路径总和
- LeetCode刷题(17)【中等】两数相加(C++)
- LeetCode·每日一题·2319.判断矩阵是否是一个X矩阵·数学
- LeetCode·每日一题·1764.通过连接另一个数组的子数组得到一个数组·模拟
- LeetCode·每日一题·864.获取所有钥匙的最短路径·广度优先搜索
- LeetCode·71.简化路径·栈模拟
- leetcode 题型 数据结构 解法 分类总结
- LeetCode-88. 合并两个有序数组(java)
- [LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和
- [LeetCode] 687. Longest Univalue Path 最长唯一值路径
- [LeetCode] 382. Linked List Random Node 链表随机节点
- [LeetCode] 231. Power of Two 2的次方数
- [LeetCode] 347. Top K Frequent Elements 前K个高频元素
- [LeetCode] 62. Unique Paths 唯一路径
- leetcode 64 最小路径和
- leetcode 63 不同路径II
- leetcode 62 不同路径
- leetcode 55 跳跃游戏