742. Closest Leaf in a Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findClosestLeaf(TreeNode root, int k) {
        Map<TreeNode, List<TreeNode>> hash = new HashMap<>();
        dfs(hash, root, null);

        Set<TreeNode> seen = new HashSet<>();
        Queue<TreeNode> q = new LinkedList<>();
        for (TreeNode node : hash.keySet()){
            if (node != null && node.val == k){
                seen.add(node);
                q.offer(node);
            }
        }

        while (!q.isEmpty()){
            TreeNode cur = q.poll();
            if (cur == null) continue;
            if (hash.get(cur).size() <= 1) return cur.val;
            for (TreeNode neighbour : hash.get(cur)){
                if (!seen.contains(neighbour)){
                    seen.add(neighbour);
                    q.offer(neighbour);
                }
            }
        }

        return -1;
    }

    private void dfs(Map<TreeNode, List<TreeNode>> hash, TreeNode root, TreeNode parent){
        if (root != null){
            if (!hash.containsKey(root)) hash.put(root, new LinkedList<>());
            if (!hash.containsKey(parent)) hash.put(parent, new LinkedList<>());
            hash.get(root).add(parent);
            hash.get(parent).add(root);
            dfs(hash, root.left, root);
            dfs(hash, root.right, root);
        }
    }
}

O(n)

721 Accounts Merge

构建graph map + BFS, M * lgM, M is the sum of each list

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {

        Map<String, String> emailToName = new HashMap<>();
        Map<String, List<String>> graph = new HashMap<>();
        for (List<String> account : accounts){

            String name = "";
            for (String str : account){
                if (name == ""){
                    name = str;
                    continue;
                }
                System.out.println("name: " + name);
                emailToName.put(str, name);    
                if (!graph.containsKey(account.get(1))){
                    List<String> temp = new ArrayList<>();
                    temp.add(str);
                    graph.put(account.get(1), temp);
                }
                else{
                    graph.get(account.get(1)).add(str);
                }
                if (!graph.containsKey(str)){
                    List<String> temp = new ArrayList<>();
                    temp.add(account.get(1));
                    graph.put(str, temp);
                }
                else{
                    graph.get(str).add(account.get(1));
                }
            }

        }

        //System.out.println("emailToName: " + emailToName.size());
        //System.out.println("graph: " + graph.size());

        Set<String> seen = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        List<List<String>> ans = new ArrayList<>();

        for (String cur : graph.keySet()){
            if (!seen.contains(cur)){

                List<String> emailList = new ArrayList<>();
                seen.add(cur);
                q.offer(cur);

                while (!q.isEmpty()){
                    String source = q.poll();
                    emailList.add(source);
                    for (String neighbour : graph.get(source)){
                        if (!seen.contains(neighbour)){
                            seen.add(neighbour);
                            q.offer(neighbour);
                        }
                    }
                }

                Collections.sort(emailList);
                emailList.add(0, emailToName.get(cur));
                ans.add(emailList);
            }
        }

        return ans;
    }
}

UnionFind, 时间复杂度一样

class Solution {

    private class UnionFind{
        int[] father;

        public UnionFind(){
            father = new int[10000];
            for (int i = 0; i < 10000; i++){
                father[i] = i;
            }
        }

        public int find(int x){
            if (father[x] == x){
                return x;
            }

            return father[x] = find(father[x]);
        }

        public void union(int a, int b){
            int father_a = find(a);
            int father_b = find(b);

            if (father_a != father_b){
                father[father_a] = father_b;
            }
        }
    }

    public List<List<String>> accountsMerge(List<List<String>> accounts) {

        UnionFind uf = new UnionFind();
        Map<String, String> emailToName = new HashMap<>();
        Map<String, Integer> emailToId = new HashMap<>();
        int id = 0;
        for (List<String> account : accounts){
            String name = "";
            for (String email : account){
                if (name == ""){
                    name = email;
                    continue;
                }
                if (!emailToId.containsKey(email)){
                    emailToId.put(email, id++);
                }
                emailToName.put(email, name);
                uf.union(emailToId.get(account.get(1)), emailToId.get(email));
            }
        }

        Map<Integer, List<String>> graph = new HashMap<>();
        for (String email : emailToName.keySet()){
            int index = uf.find(emailToId.get(email));
            if (!graph.containsKey(index)){
                List<String> temp = new ArrayList<>();
                temp.add(email);
                graph.put(index, temp);
            }
            else{
                graph.get(index).add(email);
            }
        }

        List<List<String>> ans = new ArrayList<>();
        for (List<String> emails : graph.values()){
            Collections.sort(emails);
            emails.add(0, emailToName.get(emails.get(0)));
            ans.add(emails);
        }

        return ans;
    }
}