310. Minimum Height Trees

题目

  • For a 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

    1. 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).

    2. 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 :

    1
    2
    3
    4
    5
    6
    7
    8
    9
    Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

    0
    |
    1
    / \
    2 3

    Output: [1]
  • Example 2 :

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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.

解题思路

解法1 - 暴力破解(超时Failed)

  • 步骤
    • 以每个节点都为根,对每个节点使用BFS遍历得到以该节点为根时树的高度
    • 比较各个节点时树的高度,得到Minimum Height Trees的根节点
  • 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    class Solution {
    public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
    vector<int> v;
    int edgesArray[n][n];

    int height[n];

    for(int i = 0; i < n; ++i) {
    height[i] = getHeight(n, i, edges);
    }

    // 寻找最小高度树的根节点
    int min = n;
    for(int i = 0; i < n; ++i) {
    if(height[i] < min) {
    min = height[i];
    v.clear();
    v.push_back(i);
    }
    else if(height[i] == min) {
    v.push_back(i);
    }
    }
    return v;
    }

    // bfs遍历
    int getHeight(int n, int root, vector<pair<int, int> >& edges) {
    int h = 0;
    int visited[n] = {0};
    visited[root] = 1;
    queue<int> q;
    q.push(root);
    int depth[n] = {0};
    while(!q.empty()) {
    int tmp = q.front();
    q.pop();
    for(auto iter = edges.begin(); iter != edges.end(); iter++) {
    if((*iter).first == tmp || (*iter).second == tmp) {
    int newNode = (*iter).first + (*iter).second - tmp;
    if(!visited[newNode]) {
    depth[newNode] = depth[tmp] + 1;
    q.push(newNode);
    visited[newNode] = 1;
    }
    }
    }
    }
    int max = 0;
    for(int i = 0; i < n; ++i) {
    if(depth[i] > max)
    max = depth[i];
    }
    return max;
    }
    };
  • 复杂度 — $O(V^2E)$ (V表示节点数量,E表示边的数量)
  • 结果果然超时了
    在这里插入图片描述
  • 改进与优化
    • 可以利用map数据结构,来存储每个节点对应其连接的节点所组成的一个映射map<int, vector<int> >,或者一个二维数组
    • 复杂度 — $O(VE)$ (V表示节点数量,E表示边的数量)
    • 优化的代码
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      class Solution {
      public:
      vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
      vector<int> v;
      map<int, vector<int> > myMap;

      int height[n];

      for(auto iter = edges.begin(); iter != edges.end(); iter++) {
      myMap[(*iter).first].push_back((*iter).second);
      myMap[(*iter).second].push_back((*iter).first);
      }

      for(int i = 0; i < n; ++i) {
      height[i] = getHeight(n, i, myMap);
      }

      // 寻找最小高度树的根节点
      int min = n;
      for(int i = 0; i < n; ++i) {
      if(height[i] < min) {
      min = height[i];
      v.clear();
      v.push_back(i);
      }
      else if(height[i] == min) {
      v.push_back(i);
      }
      }
      return v;
      }

      // bfs遍历
      int getHeight(int n, int root, map<int, vector<int> > myMap) {
      int h = 0;
      int visited[n] = {0};
      visited[root] = 1;
      queue<int> q;
      q.push(root);
      int depth[n] = {0};
      while(!q.empty()) {
      int tmp = q.front();
      q.pop();
      for(auto iter = myMap[tmp].begin(); iter != myMap[tmp].end(); iter++) {
      if(!visited[(*iter)]) {
      depth[(*iter)] = depth[tmp] + 1;
      q.push((*iter));
      visited[(*iter)] = 1;
      }
      }
      }
      int max = 0;
      for(int i = 0; i < n; ++i) {
      if(depth[i] > max)
      max = depth[i];
      }
      return max;
      }
      };
    • 但是依旧超时
      在这里插入图片描述

思考提示:How many MHTs can a graph have at most?

  • 每个树最多有两个MHTs。假如有三个或多个可以作为MHTs的根节点,根据树的定义,每两个节点都可以找到一条路径连接起来,树是一个强连通的图,不存在简单环,则至少一个一个或多个比其余节点高,则大于三个MHTs不成立。

解法2 — 类剥洋葱求解(AC)

  • 本方法学习自其他优秀解法
  • 步骤
    1. 建立一个映射表,记录每一个点与其直接相连的点
    2. 将树的叶节点(度为1的节点)加入一个队列中
    3. 假如当前队列中存储的节点数小于等于2,则退出循环。否则遍历队列中的每个节点。对每个节点,将其弹出队列,同时将与其相连节点的集合中将该节点删去,如果删完该节点后此节点也变成一个叶节点(度数为1),那么将这个节点加入队列中。
  • 时间复杂度 — $O(n)$
  • 实现代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    class Solution {
    public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
    if(n == 1) return {0};
    vector<int> ans;
    vector<set<int> > myVec(n);
    for(auto edge : edges) {
    myVec[edge.first].insert(edge.second);
    myVec[edge.second].insert(edge.first);
    }
    queue<int> q;
    for(int i = 0; i < n; ++i)
    if(myVec[i].size() == 1)
    q.push(i);

    while(n > 2) {
    int size = q.size();
    n -= size;
    for(int i = 0; i < size; ++i) {
    int tmp = q.front();
    q.pop();
    for (auto it : myVec[tmp]) {
    myVec[it].erase(tmp);
    if (myVec[it].size() == 1) q.push(it);
    }
    }
    }

    while(!q.empty()) {
    ans.push_back(q.front());
    q.pop();
    }

    return ans;
    }
    };