113. Path Sum II 输出每个具体路径
[抄题]: Given a binary tree and a sum,find all root-to-leaf paths where each path‘s sum equals the given sum. Note:?A leaf is a node with no children. Example: Given the below binary tree and? 5
/ 4 8
/ / 11 13 4
/ / 7 2 5 1
Return: [
[5,4,11,2],[5,8,5]
]
? ?[暴力解法]: 时间分析: 空间分析: ?[优化后]: 时间分析: 空间分析: [奇葩输出条件]: [奇葩corner case]: [思维问题]: 不知道怎么添加元素:连arraylist都忘了我去 backtracing的add-dfs-remove也忘了 [英文数据结构或算法,为什么不用别的数据结构或算法]: 嵌套类型的右边也是对应的: List<List<Integer>> result = new ArrayList<List<Integer>>(); [一句话思路]: [输入量]:空:?正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入): [画图]: [一刷]: dfs中如果是累计求和,就要求有全局变量sum。所以不如curSum每次缩小,最后变成root.val。 [二刷]: [三刷]: [四刷]: [五刷]: ? [五分钟肉眼debug的结果]: [总结]: 为了避免全局变量,所以不如curSum每次缩小,最后变成root.val。 [复杂度]:Time complexity: O(n) Space complexity: O(n) [算法思想:迭代/递归/分治/贪心]: [关键模板化代码]: [其他解法]: [Follow Up]: [LC给出的题目变变变]: ?[代码风格] : ?[是否头一次写此类driver funcion的代码] : ?[潜台词] : ? class Solution { public List<List<Integer>> pathSum(TreeNode root,int sum) { //initialization List<Integer> cur = new ArrayList<>(); List<List<Integer>> result = new ArrayList<List<Integer>>(); //corner case if (root == null) return result; dfs(root,sum,cur,result); return result; } public void dfs(TreeNode root,int curSum,List<Integer> cur,List<List<Integer>> result) { //corner case: root == null if (root == null) return ; //add to result cur.add(root.val); if (root.left == null && root.right == null && curSum == root.val) result.add(new ArrayList(cur)); else { //dfs dfs(root.left,curSum - root.val,result); dfs(root.right,curSum - root.val,result); } //remove last cur.remove(cur.size() - 1); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |