310. Minimum Height Trees[TODO]

Version #2 DP[TODO]

三刷 07/2022

Version #1 BFS

Time O(N)

Space O(N)

Runtime: 20 ms, faster than 96.83% of Java online submissions for Minimum Height Trees.

Memory Usage: 69.1 MB, less than 81.98% of Java online submissions for Minimum Height Trees.

class Solution {

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {

        int[] count = new int[n];

        List<Integer>[] graph = new ArrayList[n];

        for (int i = 0; i < n; i++) {

            graph[i] = new ArrayList<>();

        }

        for (int[] edge : edges) {

            int a = edge[0];

            int b = edge[1];

            count[a]++;

            count[b]++;

            graph[a].add(b);

            graph[b].add(a);

        }

        int visited = 0;

        Queue<Integer> que = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {

            if (count[i] <= 1) {

                que.offer(i);

                visited++;

            }

        }

        // 3 [[0,1],[0,2]]

        //  1 - 0 - 2

        while (!que.isEmpty()) {

            int size = que.size();

            if (visited == n) {

                return new ArrayList<>(que);

            }

            while (size-- > 0) {

                int curr = que.poll();

                for (Integer next : graph[curr]) {

                    if (count[next] <= 1) {

                        continue;

                    }

                    count[next]--;

                    if (count[next] == 1) {

                        que.offer(next);

                        visited++;

                    }

                }

            }

        }

        return new ArrayList<>();

    }

}

Version #1 BFS

一刷
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> result = new ArrayList<>();
if (n < 0) {
return result;
}
if (n == 1) {
result.add(0);
return result;
}
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
Queue<Integer> que = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (graph.get(i).size() == 1) {
que.offer(i);
}
}

while (n > 2) {
int size = que.size();
while (size-- > 0) {
Integer curr = que.poll();
for (Integer next : graph.get(curr)) {
graph.get(next).remove(curr);
if (graph.get(next).size() == 1) {
que.offer(next);
}
}
}
}
while (!que.isEmpty()) {
result.add(que.poll());
}
return result;
}




O(n)

For a tree we can do some thing similar. We start from every end, by end we mean vertex of degree 1 (aka leaves). We let the pointers move the same speed. When two pointers meet, we keep only one of them, until the last two pointers meet or one step away we then find the roots.

84.37 %

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return new ArrayList<Integer>(Arrays.asList(0));
        // build the graph represented by List<Set<Integer>> list of neighbors for each node
        List<Set<Integer>> neighborList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            neighborList.add(new HashSet<>());
        }
        // O(#edges)
        for (int[] edge : edges) {
            neighborList.get(edge[0]).add(edge[1]);
            neighborList.get(edge[1]).add(edge[0]);
        }
     
        Queue<Integer> que = new LinkedList<>();
        // Add leaves to que
        for(int i = 0; i < n; i++) {
            if (neighborList.get(i).size() == 1) {
                que.offer(i);
            }
        }
        while (n > 2) {
            int size = que.size();
            n -= size;
            while (size-- > 0) {
                int curr = que.poll();
                for (int neighbor : neighborList.get(curr)) {
                    Set<Integer> set = neighborList.get(neighbor);
                    set.remove(curr);
                    if (set.size() == 1) {
                        que.offer(neighbor);
                    }
                }
            }
        }
        return new ArrayList<Integer>(que);
    }
}

二刷BFS

“Basically, the idea is to eat up all the leaves at the same time, until one/two leaves are left.”

Runtime: 16 ms, faster than 68.64% of Java online submissions for Minimum Height Trees.

Memory Usage: 43.6 MB, less than 48.82% of Java online submissions for Minimum Height Trees.

class Solution {

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {

        if (n == 1) {

            return Collections.singletonList(0);

        }

        // leaf, there's only 1 edge connected to it

        // key-node, value-count of edges that touch the node

        List<Set<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {

            graph.add(new HashSet<>());

        }

        for (int[] edge : edges) {

            graph.get(edge[0]).add(edge[1]);

            graph.get(edge[1]).add(edge[0]);

        }

        Queue<Integer> que = new LinkedList<>();

        List<Integer> leaves = new ArrayList<>();

        for (int i = 0; i < graph.size(); i++) {

            if (graph.get(i).size() == 1) {

                que.offer(i);

                leaves.add(i);

            }

        }

        while (n > 2) {

            int size = que.size();

            n -= size;

            List<Integer> newLeaves = new ArrayList<>();

            while (size-- > 0) {

                int curr = que.poll();

                for (Integer neighbor : graph.get(curr)) {

                    Set<Integer> nSet = graph.get(neighbor);

                    nSet.remove(curr);

                    if (nSet.size() == 1) {

                        que.offer(neighbor);

                        newLeaves.add(neighbor);

                    }

                }

            }

            leaves = newLeaves;

        }

        return leaves;

    }

}