leetcode 310. Minimum Height Trees

朴灿烈づ我的快乐病毒、 2022-07-30 14:26 127阅读 0赞

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

Given `n = 4`, `edges = [[1, 0], [1, 2], [1, 3]]`

0
            |
            1
           / \
          2   3

return `[1]`

Example 2:

Given `n = 6`, `edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]`

0  1  2
          \ | /
            3
            |
            4
            |
            5

return `[3, 4]`

class Solution {
    	vector<vector<int>> traverse(int m, map<int, vector<int>>&pairedges,int n,int h)
    	{
    		vector<vector<int>>que;
    		vector<int>visited(n);
    		vector<int>aa; 
    		aa.push_back(m);
    		visited[m] = 1;
    		que.push_back(aa);
    		while (!que.back().empty())
    		{
    			vector<int>bb;
    			for (int i = 0; i < que.back().size(); i++)
    			{
    				for (int j =0;j< pairedges[que.back()[i]].size();j++)
    				{
    					if (visited[pairedges[que.back()[i]][j]] == 0)
    					{
    						visited[pairedges[que.back()[i]][j]] = 1;
    						bb.push_back(pairedges[que.back()[i]][j]);
    					}
    				}
    			}
    			que.push_back(bb);
    			if (que.size() >= h + 1)
    			{
    				if (que.back().empty())
    					que.pop_back();
    				return que;
    			}
    		}
    		if (que.back().empty())
    			que.pop_back();
    		return que;
    	}
    public:
    	vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
    		vector<int>re;
    		if (edges.empty())
    			{
    			re.push_back(0);
    			return re;
    		}
    		map<int, vector<int>>pairedges;
    		for (int i = 0; i < edges.size(); i++)
    		{
    			pairedges[edges[i].first].push_back(edges[i].second);
    			pairedges[edges[i].second].push_back(edges[i].first);
    		}
    		vector<vector<int>>que = traverse(edges[0].first, pairedges,n,n);
    		int m = que.back()[0];
    		que.clear();
    		que = traverse(m, pairedges,n,n);
    		int minh = que.size()/2+1;
    		int s = que.size();
    		if (s % 2 == 0)
    		{
    			for (int i = 0; i < que[s / 2 - 1].size(); i++)
    			{
    				vector<vector<int>>pp = traverse(que[s / 2 - 1][i], pairedges,n,minh);
    				if (pp.size() == minh)
    				{
    					re.push_back(que[s / 2 - 1][i]);
    					break;
    				}
    			}
    			for (int i = 0; i < que[s / 2].size(); i++)
    			{
    				vector<vector<int>>pp = traverse(que[s / 2][i], pairedges,n,minh);
    				if (pp.size() == minh)
    				{
    					re.push_back(que[s / 2][i]);
    					return re;
    				}
    			}
    		}
    		else
    		{
    			for (int i = 0; i < que[s / 2].size(); i++)
    			{
    				vector<vector<int>>pp = traverse(que[s / 2][i], pairedges,n,minh);
    				if (pp.size() == minh)
    				{
    					re.push_back(que[s / 2][i]);
    					return re;
    				}
    			}
    		}
    		return re;
    	}
    };