您的位置: 首页  >  文章  >  LeetCode 最小高度树

LeetCode 最小高度树

分类: 文章 • 2024-06-05 19:53:10

对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。

示例 1:

输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
        0
        |
        1
       / \
      2   3 

输出: [1]

示例 2:

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

输出: [3, 4]

说明:

根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

刚开始吧，我想着和求二叉树的高度一样，首先穷举所有的节点作为根节点，然后只要求出根节点到达叶节点的最长路径的长度即可，所以使用了回溯法。然而LeetCode果不出其然的使用了大量的测试数据。。。

class Solution {
public:
	int treeHeight(vector<vector<int> > &matrix, int n, int nowIndex, vector<bool> &visitedFlag) {
		int maxHeight = 1;
		for (int nextIndex = 0; nextIndex < n; ++nextIndex) {
			if (matrix[nowIndex][nextIndex] && visitedFlag[nextIndex] == false) {//如果这个节点没有访问过，且可达
				visitedFlag[nextIndex] = true;//标记访问
				maxHeight = max(maxHeight, treeHeight(matrix, n, nextIndex, visitedFlag) + 1);//继续搜索
				visitedFlag[nextIndex] = false;//取消标记访问
			}
		}
		return maxHeight;
	}
	vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
		vector<vector<int> > matrix(n, vector<int>(n, 0));//邻接矩阵（储存边的信息
		for (auto &edge : edges) {//遍历edges，将所有的边信息转化为领结矩阵的信息
			matrix[edge.first][edge.second] = matrix[edge.second][edge.first] = 1;
		}
		int minRes = INT_MAX, tempRes;
		vector<bool> visitedFlag(n, false);//visitedFlag[i]用于标记i这个节点是否访问
		vector<int> heightVec(n, 0);//resultVec[i]用于记录以第i个节点作为根，树的高度
		//穷举根节点
		for (int rootIndex = 0; rootIndex < n; ++rootIndex) {
			visitedFlag[rootIndex] = true;//标记访问
			tempRes = treeHeight(matrix, n, rootIndex, visitedFlag);//以rootIndex为根的树高度
			minRes = min(minRes, tempRes);//更新最小的数高度
			heightVec[rootIndex] = tempRes;//记录以rootIndex为根的树的高度
			visitedFlag[rootIndex] = false;//标记未访问
		}
		vector<int> result;
		//寻找所有跟根节点为minRes的树
		for (int index = 0; index < n; ++index) {
			if (heightVec[index] == minRes) {
				result.push_back(index);
			}
		}
		return result;
	}
};

LeetCode 最小高度树
然后加了几个剪枝

class Solution {
public:
	int treeHeight(vector<vector<int> > &matrix, int n, int nowIndex, vector<bool> &visitedFlag, int &minRes) {
		int maxHeight = 1;
		for (int nextIndex = 0; nextIndex < n; ++nextIndex) {
			if (matrix[nowIndex][nextIndex] && visitedFlag[nextIndex] == false && minRes > maxHeight) {//如果这个节点没有访问过，且可达
				visitedFlag[nextIndex] = true;//标记访问
				maxHeight = max(maxHeight, treeHeight(matrix, n, nextIndex, visitedFlag, minRes) + 1);//继续搜索
				visitedFlag[nextIndex] = false;//取消标记访问
			}
		}
		return maxHeight;
	}
	vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
		vector<vector<int> > matrix(n, vector<int>(n, 0));//邻接矩阵（储存边的信息
		for (auto &edge : edges) {//遍历edges，将所有的边信息转化为领结矩阵的信息
			matrix[edge.first][edge.second] = matrix[edge.second][edge.first] = 1;
		}
		int minRes = INT_MAX, tempRes;
		vector<bool> visitedFlag(n, false);//visitedFlag[i]用于标记i这个节点是否访问
		vector<int> heightVec(n, INT_MAX);//resultVec[i]用于记录以第i个节点作为根，树的高度
		//穷举根节点
		for (int rootIndex = 0; rootIndex < n; ++rootIndex) {
			visitedFlag[rootIndex] = true;//标记访问
			tempRes = treeHeight(matrix, n, rootIndex, visitedFlag, minRes);//以rootIndex为根的树高度
			minRes = min(minRes, tempRes);//更新最小的数高度
			heightVec[rootIndex] = tempRes;//记录以rootIndex为根的树的高度
			visitedFlag[rootIndex] = false;//标记未访问
		}
		vector<int> result;
		//寻找所有跟根节点为minRes的树
		for (int index = 0; index < n; ++index) {
			if (heightVec[index] == minRes) {
				result.push_back(index);
			}
		}
		return result;
	}
};

LeetCode 最小高度树
蛋试仔细分析会发现，在无向图中，最多只有两个根节点符合此题的要求，并且符合要求的节点必定不是叶节点。
LeetCode 最小高度树
后面在评论区翻出了大牛的代码，设立一个点集，保存当前图中度为1的点，即树的叶子结点。然后将这些结点从图中删去，此时，有可能会生成一些新的叶子结点，那么再将这些新的叶子结点加入点集中。不断重复这个过程，直到图中的剩下的点不超过3个。为什么是3个呢？举个例子，假设一个图有两个点，用一条边连起来，那么返回的结果就是这两个点。但如果图中有三个点，用两条边连起来，那么返回的结果就是中间的那一个点。

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
		vector<int> res;
		vector<int> indegree(n,0);//储存每个点的度 
		unordered_map<int,vector<int> > hash;//储存图中边的信息 
		for(int i=0;i<edges.size();i++){
			//建图并统计点的度 
			hash[edges[i].first].push_back(edges[i].second);
			hash[edges[i].second].push_back(edges[i].first);
			indegree[edges[i].first]++;
			indegree[edges[i].second]++;
		}
		while(n>2)//最多含有两个节点
		{
			vector<int> vec;
			//找到当前的所有叶子结点 
			for(int i=0;i<indegree.size();i++)
				if(indegree[i]==1)
					vec.push_back(i);
			for(int i=0;i<vec.size();i++)
			{
				//删去这个叶子结点，并将与之相连的点的度自减1
				indegree[vec[i]]=-1;
				n--;
				for(int j=0;j<hash[vec[i]].size();j++)
					indegree[hash[vec[i]][j]]--;
			}
		}
		for(int i=0;i<indegree.size();i++)
			if(indegree[i]>=0)
				res.push_back(i);
		return res;
    }
};

版本二：

class Solution {
public:
	vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
		if (n == 1) return{ 0 };
		vector<int> res;
		vector<unordered_set<int>> adj(n);
		queue<int> q;
		for (auto &edge : edges)//复制边信息
		{
			adj[edge.first].insert(edge.second);
			adj[edge.second].insert(edge.first);
		}
		//将只有一条边与其连接的某个数放入队列q中
		for (int i = 0; i < n; ++i) //for里面嵌if必须加括号
		{
			if (adj[i].size() == 1) 
				q.push(i);
		}
		while (n > 2) //将外围的数字全部剔除，
		{
			int size = q.size();
			n -= size;
			for (int i = 0; i < size; ++i) //先将仅连接单个边的数进行处理，假定为a
			{
				int t = q.front(); q.pop();
				for (auto a : adj[t])
				{
					adj[a].erase(t);
					if (adj[a].size() == 1) 
						q.push(a);//若这单个边连接的另一头除了与a链接外，仅剩一个点b与其链接，就将b放入队列。
				}
			}
		}
		while (!q.empty())
		{
			res.push_back(q.front()); 
			q.pop();
		}
		return res;
	}
};

相关推荐