[Leetcode]310. Minimum Height Trees(C++)

题目描述

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.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs' root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

例子

例子见上方原题链接。

Constraints

1 <= n <= 2 * 10^4

edges.length == n - 1

0 <= ai, bi < n

ai != bi

All the pairs (ai, bi) are distinct.

The given input is guaranteed to be a tree and there will be no repeated edges.

解题思路

这道题给定条件是保证输入是一个合法的树，因此暴力解法是以每个节点为根节点使用广度优先搜索往下遍历，求出高度。并根据高度筛选出结果。每次遍历时间复杂度是 O(n) 因此最后复杂度是 O(n)。根据给定的数据规模判断不可行。

我们可以转换思路，虽然每个节点都有可能是根节点，但是根据例子来看，当节点数大于3时，最小高度树的根节点的边数都不为1，这很好理解，为了让高度最小，从根节点开始每一层都应该有尽量多的节点。因此我们可以从叶节点（只有一条边）出发往上遍历，每次遍历一个节点叶节点时将其链接的边去除，如果去除后其邻居的边数只有1，表示找到了一个新的叶节点。每一次循环相当于从外部向内部去除了一层最外层叶节点，当最后遍历结束后，最后一次遍历的叶节点都可以作为根节点。

代码如下：

#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>

class Solution {
public:
    std::vector<int> findMinHeightTrees(int n,
                                        std::vector<std::vector<int>>& edges) {
        std::vector<int> roots;

        std::vector<std::unordered_set<int>> graph(n);

        for (auto edge : edges) {
            graph[edge[0]].insert(edge[1]);
            graph[edge[1]].insert(edge[0]);
        }

        std::queue<int> leaves;
        std::unordered_set<int> visited;

        for (int i = 0; i < n; ++i) {
            if (graph[i].size() == 1) {
                leaves.push(i);
            } else if (graph[i].empty()) {
                return {i};
            }
        }

        while (!leaves.empty()) {
            std::queue<int> next_leaves;

            while (!leaves.empty()) {
                int node = leaves.front();
                leaves.pop();
                roots.push_back(node);
                for (int nei : graph[node]) {
                    // remove this edge
                    graph[nei].erase(node);
                    // if it becomes a new node, add it to the queue
                    if (graph[nei].size() == 1) {
                        next_leaves.push(nei);
                    }
                }
                graph[node].clear();
            }

            if (!next_leaves.empty()) {
                roots.clear();
                std::swap(next_leaves, leaves);
            }
        }
        return roots;
    }
};

时间复杂度: O(|E|+|N|)
空间复杂度: O(|E|+|N|)

GitHub 代码同步地址： 310.MinimumHeightTrees.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions