class Solution { public: vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) { vector<vector<int>> graph(n); vector<int> indegree(n, 0), ans; for(auto e : edges){ graph[e[0]].push_back(e[1]); graph[e[1]].push_back(e[0]); indegree[e[0]]++; indegree[e[1]]++; } queue<int> q; for(int i = 0; i < n ;i++) if(indegree[i] == 1) q.push(i), indegree[i]--; while(!q.empty()){ int s = q.size(); ans.clear(); for(int i = 0 ; i < s ;i++){ int curr = q.front(); q.pop(); ans.push_back(curr); for(auto child : graph[curr]) { indegree[child]--; if(indegree[child] == 1) q.push(child); } } } if(n == 1)ans.push_back(0); return ans; } };
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter