算法打卡:第9周
2021/5/15 12:27:08
本文主要是介绍算法打卡:第9周,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题一
剑指Offer 34.二叉树中和为某一值的路径:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
思路:递归遍历并保存所有路径,然后计算符合要求的路径。
public List<List<Integer>> pathSum(TreeNode root, int target) { if (root == null) { return new ArrayList<>(); } List<List<Integer>> list = this.recursion(root); Iterator<List<Integer>> it = list.iterator(); while (it.hasNext()) { List<Integer> path = it.next(); int sum = path.stream().mapToInt(Integer::intValue).sum(); if (sum != target) { it.remove(); } else { Collections.reverse(path); } } return list; } public List<List<Integer>> recursion(TreeNode root) { List<List<Integer>> list = new ArrayList<>(); if (root.left == null && root.right == null) { List<Integer> path = new ArrayList<>(); list.add(path); } else { if (root.left != null) { list.addAll(this.recursion(root.left)); } if (root.right != null) { list.addAll(this.recursion(root.right)); } } for (List<Integer> path : list) { path.add(root.val); } return list; }
问题二
特定深度节点链表:https://leetcode-cn.com/problems/list-of-depth-lcci/
思路:递归遍历,使用map保存所有层的节点信息。然后转化为ListNode
public ListNode[] listOfDepth(TreeNode tree) { if (tree == null) { return new ListNode[0]; } Map<Integer, List<Integer>> map = new HashMap<>(); this.recursion(map, tree, 1); ListNode[] listNode = new ListNode[map.size()]; for (int i = 1; i <= map.size(); i++) { List<Integer> list = map.get(i); if (list == null) { break; } ListNode root = new ListNode(-1); ListNode curr = root; for (Integer node : list) { curr.next = new ListNode(node); curr = curr.next; } listNode[i - 1] = root.next; } return listNode; } public void recursion(Map<Integer, List<Integer>> map, TreeNode root, int depth) { List<Integer> list = map.get(depth); if (list == null) { list = new ArrayList<>(); map.put(depth, list); } list.add(root.val); depth++; if (root.left != null) { this.recursion(map, root.left, depth); } if (root.right != null) { this.recursion(map, root.right, depth); } }
这篇关于算法打卡:第9周的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现