[leetcode] 310. Minimum Height Trees

[leetcode] 310. Minimum Height Trees

Description

For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1 :

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]] 0 | 1 / \ 2 3 Output: [1]

Example 2 :

Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]] 0 1 2 \ | / 3 | 4 | 5 Output: [3, 4]

Note:

According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

分析

题目的意思是：找出所有最小高度树的根结点。

类似剥洋葱的方法，就是一层一层的褪去叶节点，最后剩下的一个或两个节点就是我们要求的最小高度树的根节点。

代码

class Solution {public: vector findMinHeightTrees(int n, vector>& edges) { if(n==1) return {0}; vector res; vector> adj(n); queue q; for(auto edge:edges){ adj[edge.first].insert(edge.second); adj[edge.second].insert(edge.first); } for(int i=0;i2){ //erase nodes from outword to inword int cnt=q.size(); n-=cnt; for(int i=0;i

参考文献

​​[LeetCode] Minimum Height Trees 最小高度树​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。