美文网首页
Minimum Height Trees

Minimum Height Trees

作者: 我叫胆小我喜欢小心 | 来源:发表于2017-04-24 15:40 被阅读50次

    题目来源
    给一个图,求一个根节点使得这棵树的高度最低。
    头还有点晕…感觉不能思考…这道题怎么做,看了tags还是不懂。
    看看讨论区吧。
    主要是一个广度优先搜索的思想,设置多个指针,从叶子节点往里遍历,直到最后只剩下俩指针指向同一个节点或者相差一个节点。
    代码如下:

    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            if (n == 1)
                return vector<int>{0};
            unordered_map<int, unordered_set<int>> adj;
            for (auto edge : edges) {
                adj[edge.first].insert(edge.second);
                adj[edge.second].insert(edge.first);
            }
            vector<int> leaves;
            for (auto item : adj) {
                if (item.second.size() == 1)
                    leaves.push_back(item.first);
            }
            while (n > 2) {
                n -= leaves.size();
                vector<int> newLeaves;
                for (auto leaf : leaves) {
                    int nextNode = *adj[leaf].begin();
                    adj[leaf].erase(nextNode);
                    adj[nextNode].erase(leaf);
                    if (adj[nextNode].size() == 1)
                        newLeaves.push_back(nextNode);
                }
                leaves = newLeaves;
            }
            return leaves;
        }
    };
    

    相关文章

      网友评论

          本文标题:Minimum Height Trees

          本文链接:https://www.haomeiwen.com/subject/rbkpzttx.html