[LinttCode]The Barycentre Of The Trees

这道题和Fermat Point of Graphs是一样的，我们先选取任意节点当根节点，比如编号为0的节点，我们计算在这个情况下每个以i为根的subtree的size，记为size[i]。显而易见的是，size[i]  = sum(size[j]) + 1，j为i的子节点。我们用第一次DFS构建size数组。之后第二次我们同样从0号节点开始DFS，那么以r节点为根节点的情况下，r的所有子树中size最大的那一个res[r] = max(max(size[j]), N - size[i])，j是i的子节点，N为节点总数。我们取res中最大的那一个即可。
时间复杂度为建图和两次DFS，O(N)。空间复杂度同样，代码如下：

	class Solution {
	public:
	/**
	* @param x: The vertexes of the edges
	* @param y: The vertexes of the edges
	* @return: Return the index of barycentre
	*/
	int getBarycentre(vector<int> &x, vector<int> &y) {
	//pick random node r as root and start dfs from it, size[i] represent the
	//size of subtree with i as its root.
	//size[i] = sum(size[j] + 1), where j is i's child
	//max subtree size when we pick i as root = max(max(size[j]), N - size[i]),
	//where j is root of i in first dfs, N is total # of nodes
	int N = x.size() + 1;
	vector<int> sz(N + 1, 0);
	vector<vector<int>> g(N + 1);
	for (int i = 0; i < N - 1; ++i)
	{
	int u = x[i], v = y[i];
	g[u].push_back(v);
	g[v].push_back(u);
	}
	getSize(g, sz, 0, 1);
	int res = -1, minSize = N;
	getRes(g, sz, 0, 1, res, minSize);
	return res;
	}
	private:
	void getSize(vector<vector<int>>& g, vector<int>& sz, int from, int to)
	{
	sz[to] = 1;
	for (const auto& adj : g[to])
	{
	if (adj != from)
	{
	getSize(g, sz, to, adj);
	sz[to] += sz[adj];
	}
	}
	}
	void getRes(vector<vector<int>>& g, vector<int>& sz, int from, int to, int& res, int& minSize)
	{
	int currSize = 0, N = g.size() - 1;
	for (const auto& adj : g[to])
	{
	if (adj != from)
	{
	getRes(g, sz, to, adj, res, minSize);
	currSize = max(currSize, sz[adj]);
	}
	}
	currSize = max(currSize, N - sz[to]);
	if (currSize < minSize || currSize == minSize && to < res)
	{
	res = to;
	minSize = currSize;
	}
	}
	};

view raw The Barycentre Of The Trees.cpp hosted with ❤ by GitHub