algorithm001
diff --git a/Week_02/id_118/NOTE.md b/Week_02/id_118/NOTE.md
@@ -1 +1,3 @@
-# 学习笔记
+# 学习笔记
+
+这周学习比较大的感触是：把你想到的先写下来/画下来，解题思路都能从这些想法中得到启发。
diff --git a/Week_02/id_118/img/图示-263.png b/Week_02/id_118/img/图示-263.png
diff --git a/Week_02/id_118/img/图示-671.png b/Week_02/id_118/img/图示-671.png
diff --git a/Week_02/id_118/img/图示-863.png b/Week_02/id_118/img/图示-863.png
diff --git a/Week_02/id_118/img/思维导图-263.671.863.png b/Week_02/id_118/img/思维导图-263.671.863.png
diff --git a/Week_02/id_118/leetcode_236_118.java b/Week_02/id_118/leetcode_236_118.java
@@ -0,0 +1,55 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+// https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/submissions/
+// 236.二叉树的最近公共祖先
+class Solution {
+    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
+
+        // root有任何一个是根节点，则它本身就是最近公共祖先
+        if(p==root || q==root){
+            return root;
+        }
+
+        // 判断：p和q在不在左子树上
+        boolean pLeft = find(root.left,p);
+        boolean qLeft = find(root.left,q);
+
+        if(pLeft && qLeft){
+            // 都在左子树
+            return lowestCommonAncestor(root.left,p,q);
+        }else if(!pLeft && !qLeft){
+            // 都在右子树
+            return lowestCommonAncestor(root.right,p,q);
+        }else{
+            // 一个在左子树，一个在右子树，则当前节点就是最近公共祖先。
+            return root;
+        }
+
+    }
+
+    // 检查 root这棵树中，是否有节点x
+    boolean find(TreeNode root, TreeNode x){
+        if(root==null){
+            return false;
+        }
+        if(root==x){
+            return true;
+        }
+        if(root.left==null && root.right==null){
+            return false;
+        }else if(root.left==null && root.right!=null){
+            return find(root.right,x);
+        }else if(root.left!=null && root.right==null){
+            return find(root.left,x);
+        }else{
+            return find(root.left,x) || find(root.right,x);
+        }        
+    }
+}
diff --git a/Week_02/id_118/leetcode_242_118.java b/Week_02/id_118/leetcode_242_118.java
@@ -0,0 +1,42 @@
+// https://leetcode-cn.com/problems/valid-anagram/submissions/
+// 有效的字母异位词
+class Solution {
+    public boolean isAnagram(String s, String t) {
+        // 考察题型：哈希表
+        // （1）把26个字母作为 key，出现次数作为 value，初始值为0表示没出现过或互相抵消了。
+        // （2）遍历 s，做 value++；再遍历 t，做 value--。这过程中如果有 value 被减成负的，直接返回 false
+        // （3）然后扫描一遍哈希表，如果有非0元素，则false。
+
+        // 1. 边界条件，若字符长度不一样，则直接返回
+        if(s.length() != t.length()){
+            return false;
+        }
+
+        // 2. 定义哈希表（java语言不需要单独做初始化操作，默认值就是0）
+        int[] hash_map = new int[27];
+
+        // 3. 第一遍扫描
+        for(int i=0;i<s.length();i++){
+            int key = s.charAt(i)-'a';
+            hash_map[key] += 1;
+        }
+
+        // 4. 第二遍扫描
+        for(int i=0;i<t.length();i++){
+            int key = t.charAt(i)-'a';
+            if(hash_map[key]==0){
+                return false;
+            }
+            hash_map[key] -= 1;
+        }
+
+        // 5.扫描哈希表
+        for(int i=0;i<27;i++){
+            if(hash_map[i]!=0){
+                return false;
+            }
+        }
+
+        return true;
+    }
+}
diff --git a/Week_02/id_118/leetcode_671_118.java b/Week_02/id_118/leetcode_671_118.java
@@ -0,0 +1,53 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+// https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/
+// 671.二叉树中第二小的节点
+class Solution {
+    public int findSecondMinimumValue(TreeNode root) {
+        // 根节点一定是最小值
+        // 若树中所有节点同值，则没有第二小
+        // 若树中根节点和子节点值不同，则第二小要么在左子树，要么在右子树
+
+        if(root == null || (root.left == null && root.right == null)){
+            return -1;
+        }
+
+        int val_root = root.val;
+        int val_left = root.left.val;
+        int val_right = root.right.val;
+
+        if(val_root!=val_left && val_root!=val_right){
+            // 左右子树根节点均与当前根节点不等值，则其一就是第二小
+            return getMinOne(val_left,val_right);
+        }else if(val_root==val_left && val_root!=val_right){
+            // 左子树根节点与当前根节点同值，右子树根节点与当前根节点不同值，则左子树取第二小，与右子树根节点比。
+            // 注意，左子树如果没有第二小，会返回负数
+            return getMinOne(findSecondMinimumValue(root.left),val_right);
+        }else if(val_root!=val_left && val_root==val_right){
+            // 类似上面的
+            return getMinOne(val_left,findSecondMinimumValue(root.right));
+        }else{
+            return getMinOne(findSecondMinimumValue(root.left),findSecondMinimumValue(root.right));
+        }  
+
+    }
+
+    int getMinOne(int x,int y ){
+        if(x==-1 && y==-1){
+            return -1;
+        }else if(x==-1 && y!=-1){
+            return y;
+        }else if(x!=-1 && y==-1){
+            return x;
+        }else{
+            return Math.min(x,y);
+        }
+    }
+}
diff --git a/Week_02/id_118/leetcode_692_118.java b/Week_02/id_118/leetcode_692_118.java
@@ -0,0 +1,154 @@
+// https://leetcode-cn.com/problems/top-k-frequent-words/submissions/
+// 692.前k个高频单词
+// 这是拿到题目后的最快想出来的思路。晚点再想想有没有别的做法。
+class Solution {
+    class LinkNode{
+        String val;
+        LinkNode next;
+        LinkNode(String s){
+            val = s;
+        }
+    }
+
+    public List<String> topKFrequent(String[] words, int k) {
+        List<String> result_list = new LinkedList();
+
+        // 1. 统计词频表和最大词频出现次数
+        Map<String,Integer> frequency_map = new HashMap();// 词频表：key：单词，value：单词出现次数。
+        int most_frequent = 0;
+
+        for(int i=0;i<words.length;i++){
+            String word = words[i];
+            if(frequency_map.containsKey(word)){
+                frequency_map.put(word,frequency_map.get(word)+1);
+            }else{
+                frequency_map.put(word,1);
+            }
+            most_frequent = Math.max(frequency_map.get(word),most_frequent);
+        }
+
+        // 2. 生成哈希表：下标 i 表示出现次数，值是出现 i 次的单词列表（这里是用链表表示的，字典序有序，初始为null）
+        LinkNode[] frequency_list = new LinkNode[most_frequent+1];
+        for (String key : frequency_map.keySet()) {
+            int frequent = frequency_map.get(key);
+            frequency_list[frequent] = build(frequency_list[frequent],key);
+        }
+
+        // 3. 逆序扫描哈希表，总共输出k个单词
+        for(int i=most_frequent;i>=0;i--){
+            LinkNode link = frequency_list[i];
+            if(link==null){
+                continue;
+            }
+            while(k!=0 && link!=null){
+                result_list.add(link.val);
+                k--;
+                link = link.next;
+            }
+        }
+
+        // 4. 这就是k个单词了
+        return result_list;
+    }
+
+    //-------------------------------------------
+
+    // 新节点插入链表，字典序有序。
+    LinkNode build(LinkNode head,String s){
+        // 如果原始链表为空，则直接 new 一个节点回去
+        if(head==null){
+            return new LinkNode(s);
+        }
+
+        // 否则的话，要找到合适的位置插入
+        LinkNode tmp = new LinkNode(s);
+
+        // 若s应该在头结点前面，即 s > head.val
+        // System.out.println("---单词比较，s="+s+" head="+head.val+" 左侧比较小？"+leftIsSmaller(s,head.val));
+        if(leftIsSmaller(s,head.val)){
+            tmp.next = head;
+            head = tmp;
+            return head;
+        }
+
+        // 否则，s应该再头结点后面。then：
+        LinkNode pre = head;
+        LinkNode current = head.next;
+        while(current!=null){
+            // System.out.println("---单词比较，s="+s+" head="+current.val+" 左侧比较小？"+leftIsSmaller(s,current.val));
+            if(leftIsSmaller(s,current.val)){
+                // s应该在 current 前面
+                pre.next = tmp;
+                tmp.next = current;
+                return head;
+            }
+            pre = pre.next;
+            current = current.next;
+        }
+
+        // 如果在中间没找到，那就是直接插到结尾
+        pre.next = tmp;
+        return head;
+
+    }
+
+
+    //-------------------------------------------
+
+
+    // 手动撸了一个字典序排序。。。心累。。。
+    boolean leftIsSmaller(String x,String y){
+        int i=0;
+        while(i<x.length() && i<y.length()){
+            int xc = x.charAt(i);
+            int yc = y.charAt(i);
+            if(xc==yc){
+                i++;
+                continue;// 注意啊，这里不能退出，得去比较下一个
+            }else if(xc<yc){
+                return true;
+            }else{
+                return false;
+            }
+        }
+        // 注意，这里是 <=，不是 <
+        if(x.length()<=i){
+            return true;
+        }else{
+            return false;
+        }
+    }
+
+
+    //-------------------------------------------
+    // 请不要管我，我是 debug 用的
+    //-------------------------------------------
+
+    void print(Map<String,Integer> map){
+        for (String key : map.keySet()) {
+            System.out.println("单词-出现次数："+key+" - "+map.get(key));
+        }
+    }
+
+
+    void print(LinkNode[] list){
+        for(int i=0;i<list.length;i++){
+            System.out.print("- "+i+"：");
+            LinkNode tmp = list[i];
+            while(tmp!=null){
+                System.out.print("->"+tmp.val);
+                tmp = tmp.next;
+            }
+            System.out.println();
+        }
+    }
+
+    void print(LinkNode head){
+        LinkNode tmp = head;
+        while(tmp!=null){
+            System.out.print("->"+tmp.val);
+            tmp = tmp.next;
+        }
+        System.out.println();
+    }
+}