Skip to content

Commit ffd786c

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request #414 from bugcodes/master
049_week02_homework
2 parents 0b87f84 + 068352a commit ffd786c

3 files changed

Lines changed: 141 additions & 1 deletion

File tree

‎Week_02/id_49/LeetCode_609_49.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package com.v0ex.leetcode;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashMap;
5+
import java.util.List;
6+
import java.util.Map;
7+
8+
/**
9+
* Find Duplicate File in System
10+
*
11+
* @author bugcoder
12+
*/
13+
public class LeetCode_609_49 {
14+
15+
/**
16+
* 用哈希表来处理，key就是文件的内容，value就是文件的路径
17+
* @param paths
18+
* @return
19+
*/
20+
public List<List<String>> findDuplicate(String[] paths) {
21+
Map<String,List<String>> map = new HashMap<>();
22+
for (String path : paths) {
23+
String[] split = path.split(" ");
24+
String rootPath = split[0]+"/";
25+
for (int i = 1; i < split.length; i++) {
26+
String file = split[i];
27+
String fileName = file.substring(0,file.indexOf("("));
28+
//拆分字符串获取文件的内容
29+
String fileContent = file.substring(file.indexOf("(")+1, file.lastIndexOf(")"));
30+
//获取文件的全部路径
31+
String filePath = rootPath + fileName;
32+
if (map.containsKey(fileContent)){
33+
List<String> list = map.get(fileContent);
34+
list.add(filePath);
35+
map.put(fileContent,list);
36+
}else {
37+
List<String> list = new ArrayList<>();
38+
list.add(filePath);
39+
map.put(fileContent,list);
40+
}
41+
}
42+
}
43+
List<List<String>> result = new ArrayList<>();
44+
for (Map.Entry<String,List<String>> entry : map.entrySet()){
45+
if (entry.getValue().size()>1){
46+
result.add(entry.getValue());
47+
}
48+
}
49+
return result;
50+
}
51+
}

‎Week_02/id_49/LeetCode_671_49.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.v0ex.leetcode;
2+
3+
import java.util.HashSet;
4+
import java.util.Set;
5+
6+
/**
7+
* Second Minimum Node In a Binary Tree
8+
*
9+
* @author bugcoder
10+
*/
11+
public class LeetCode_671_49 {
12+
13+
public int findSecondMinimumValue(TreeNode root) {
14+
Set<Integer> set = new HashSet<Integer>();
15+
inOrder(root,set);
16+
if(set.size() < 2){
17+
return -1;
18+
}
19+
//根据题意，第一个值肯定是最小的值
20+
int first = root.val;
21+
//先临时设置第二小的值是整数的最大值，后续会对这个值进行替换
22+
int second = Integer.MAX_VALUE;
23+
for(int val : set){
24+
if(first < val && val <= second){
25+
second = val;
26+
}
27+
}
28+
return second <= Integer.MAX_VALUE ? second : -1;
29+
}
30+
31+
/**
32+
* 中序遍历二叉树，把所有的值存放在Set集合中
33+
* @param root
34+
* @param set
35+
*/
36+
private void inOrder(TreeNode root,Set<Integer> set){
37+
if(root == null){
38+
return;
39+
}
40+
inOrder(root.left,set);
41+
set.add(root.val);
42+
inOrder(root.right,set);
43+
}
44+
}

‎Week_02/id_49/NOTE.md‎

Lines changed: 46 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,46 @@
1-
# 学习笔记
1+
# 学习笔记
2+
之前对于二叉树的前中后遍历，一直停留在学生时代，给定一个二叉树，能够从ABCD中选出正确答案，但是要写出递归代码，总是把自己给递进去归不来，那种深深的挫败感一直停留在对算法的黑洞里。第二周的作业，在求解LeetCode671. Second Minimum Node In a Binary Tree时，忽然想到了王争老师第三章的课件中对于二叉树遍历的讲解，四五行代码，那种感觉，简单优雅，豁然开朗。于我个人而言，这是我这周最大的收获！
3+
4+
二叉树的中遍历
5+
6+
void inOrder(TreeNode root){
7+
if(null == root){
8+
return;
9+
}
10+
//先-左节点
11+
inOrder(root.left);
12+
//然后-根节点，得到当前节点的val，进行相关的逻辑处理
13+
root.val;
14+
//最后-右节点
15+
inOrder(root.right);
16+
}
17+
18+
二叉树的前序遍历
19+
20+
void preOrder(TreeNode root){
21+
if(null == root){
22+
return;
23+
}
24+
//先-根节点，得到当前节点的val，进行相关的逻辑处理
25+
root.val;
26+
//然后-左节点
27+
inOrder(root.left);
28+
//最后-右节点
29+
inOrder(root.right);
30+
}
31+
32+
二叉树的后序遍历
33+
34+
void lastOrder(TreeNode root){
35+
if(null == root){
36+
return;
37+
}
38+
//先-左节点
39+
inOrder(root.left);
40+
//然后-右节点
41+
inOrder(root.right);
42+
//最后-根节点，得到当前节点的val，进行相关的逻辑处理
43+
root.val;
44+
}
45+
46+
二叉树的前中后序遍历可以把二叉树表示为数组，那如果知道某个二叉树的前序数组和中序数据，如何还原二叉树?

0 commit comments

Comments
 (0)