Swift solution - BFS


  • 0
    class Solution {
        func findMinHeightTrees(_ n: Int, _ edges: [[Int]]) -> [Int] {
            if n == 1 {
                return [0]
            }
            
            var adj = [Set<Int>](repeatElement(Set<Int>(), count: n))
            var leaves = [Int]()
            var count = n
            
            for edge in edges {
                adj[edge[0]].insert(edge[1])
                adj[edge[1]].insert(edge[0])
            }
            for i in 0..<n {
                if adj[i].count == 1 {
                    leaves.append(i)
                }
            }
            while count > 2 {
                count -= leaves.count
                var newLeaves = [Int]()
                for leaf in leaves {
                    let node = adj[leaf].first!
                    adj[node].remove(leaf)
                    if adj[node].count == 1 {
                        newLeaves.append(node)
                    }
                }
                leaves = newLeaves
            }
            
            return leaves
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.