minimum-height-trees.cpp (2542B)
1 class Solution { 2 public: 3 vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) { 4 // tree with n nodes 5 // 0 -> n-1 6 // n-1 edges (deductively) 7 // edges[i] = [a_i, b_i] - edge from a_i -> b_i 8 // we can select any node to be the root (as is the case with trees) 9 // a minimum height tree is a tree that has the minimal height per the 10 // root selection. 11 // return a list of all mht root labels 12 // any order 13 14 15 // peeling: 16 // start at the leaf nodes 17 // perform bfs starting from the leaf nodes, peeling as we go 18 // once there are either 1 or 2 nodes left we know these are the MHTs 19 20 vector<int> leaves = {}; 21 22 vector<int> edgeCounts(n); 23 24 vector<vector<int>> adjacencyList(n); 25 26 for(auto edge: edges) { 27 edgeCounts[edge[0]] += 1; 28 edgeCounts[edge[1]] += 1; 29 adjacencyList[edge[0]].push_back(edge[1]); 30 adjacencyList[edge[1]].push_back(edge[0]); 31 } 32 33 int remaining = n; 34 35 vector<int> checkList = {}; 36 for(int i = 0 ; i < n ; ++i) { 37 checkList.push_back(i); 38 } 39 40 getLeaves(n, leaves, checkList, edgeCounts, adjacencyList); 41 remaining -= leaves.size(); 42 43 int i = 0; 44 45 // remaining is the number that haven't been in the leaves list. 46 // once remaining == 0 we are done. 47 48 while (remaining > 0) { 49 leaves.clear(); 50 getLeaves(n, leaves, checkList, edgeCounts, adjacencyList); 51 remaining -= leaves.size(); 52 } 53 54 return leaves; 55 } 56 private: 57 void getLeaves(int n, vector<int>& leaves, vector<int>& checkList, vector<int>& edgeCounts, vector<vector<int>>& adjacencyList) { 58 for(int vertex: checkList) { 59 if(edgeCounts[vertex] == 1 || edgeCounts[vertex] == 0) { 60 leaves.push_back(vertex); 61 // differentiate between orphan node and removed leaves 62 edgeCounts[vertex] = -1; 63 } 64 } 65 66 checkList.clear(); 67 68 for(auto leaf: leaves) { 69 // cut edges at the end so we don't change tree under us 70 for(auto connected: adjacencyList[leaf]) { 71 edgeCounts[connected] -= 1; 72 if (edgeCounts[connected] == 1) { 73 checkList.push_back(connected); 74 } 75 } 76 } 77 78 } 79 };