C++ bfs solution by finding the longest path in the tree

• Basic idea: the roots of MHT must be the mid points of the longest leaf to leaf path in the tree. And to find the longest path, we can first find the farthest leaf from any node, and then find the farthest leaf from the node found above. Then these two nodes we found are the end points of the longest path. And last, we find the centers of the longest path.

EDIT: according to @hellotest solution

``````class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
//find the longest path in the tree
vector<vector<int>> lists(n);
for(auto p : edges) {
lists[p.first].push_back(p.second);
lists[p.second].push_back(p.first);
}

int len;
vector<int> prev(n, 0);
int f1 = findFarthestLeaf(lists, 0, len, prev);
int f2 = findFarthestLeaf(lists, f1, len, prev);

//find the mid
for(int i = 0; i < (len - 1) / 2; ++i) {
f2 = prev[f2];
}
if(len % 2) return vector<int>{f2};
else return vector<int>{f2, prev[f2]};
}

int findFarthestLeaf(vector<vector<int>>& lists, int id, int& len, vector<int>& prev) {
int n = lists.size();

vector<bool> visited(n, 0);
visited[id] = true;
prev[id] = id;

queue<int> q;
q.push(id);

len = 0;
int leaf;
while( !q.empty() ) {
len++;
int size = q.size();
while(size-- > 0) {
int f = q.front();
q.pop();
leaf = f;
for (int i : lists[f]) {
if (!visited[i]) {
visited[i] = true;
q.push(i);
prev[i] = f;
}
}
}
}

return leaf;
}
};
``````

• @hwf Some improvements for this approach, may not be the best, but at least avoid the second loop to check the dist to find the farthest leaf.

``````class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if (n==1) return {0};
vector<vector<int>> adj(n);
vector<int> res;
for (auto &e : edges) {
adj[e.first].push_back(e.second);
adj[e.second].push_back(e.first);
}
// two (BFS) traverses to find two ends of the longest path!
int len=0;
vector<int> prev(n, 0); // for node i, prev[i] is the previous node along the direction
int end1 = BFS(adj, 0, len, prev);
int end2 = BFS(adj, end1, len, prev);
// find the midpts based on prev info.
int mid=end2;
for (int i=1; i<=(len-1)/2; ++i) { // walk (len-1)/2 steps to find mid
mid = prev[mid];
}
res.push_back(mid);
if ((len & 1)==0) res.push_back(prev[mid]); // len is even
return res;
}
private:
int BFS(vector<vector<int>>& adj, int start, int& len, vector<int>& prev) {
// find the farthest leaf starting from start
int res; // farthest leaf
len=0; // we will call this function twice so reset it to be 0
vector<bool> visited(prev.size(), false);
queue<int> q;
q.push(start);
// level order BFS
int node;
while (!q.empty()) {
int size=q.size();
for (int i=0; i<size; ++i) { // level by level
node=q.front();
q.pop();
visited[node]=true;
for (int x : adj[node]) { // check neighbors of node
if (visited[x]) continue;
prev[x]=node;
q.push(x);
}
}
++len;
}
res=node; // the last visited node will be the farthest leaf
return res;
}
};
``````

• @hellotest Just for practice purpose, rewrite in DFS without using unordered_set, otherwise DFS part could be further simplified. And it seems pretty annoying to reset some data because we need to call two consecutive DFS.

``````class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if (n==1) return {0};
vector<vector<int>> adj(n);
vector<int> res;
for (auto &e : edges) {
adj[e.first].push_back(e.second);
adj[e.second].push_back(e.first);
}
// two (DFS) traverses to find two ends of the longest path!
vector<int> prev(n, 0);
vector<bool> visited(n, false);
int depth=0, start=0, end=0;
DFS(adj, start, end, 0, depth, prev, visited);
for (int i=0; i<n; ++i) { // reset visited
visited[i]=false;
}
start=end; depth=0; // reset
DFS(adj, start, end, 0, depth, prev, visited);
// find the midpts based on prev info.
int mid=end;
for (int i=1; i<=(depth-1)/2; ++i) { // walk (depth-1)/2 steps to find mid
mid = prev[mid];
}
res.push_back(mid);
if ((depth & 1)==0) res.push_back(prev[mid]); // depth is even
return res;
}
private:
void DFS(vector<vector<int>>& adj, int id, int& end, int level, int& depth, vector<int>& prev, vector<bool>& visited) {
// preorder recursive
int res;
level++;
visited[id]=true;
// base case: check whether we reach a leaf, if so update depth
bool leaf=true;
for (int x : adj[id]) {
if (visited[x]==false) leaf=false;
}
if (leaf) {
if (level>depth) {
depth=level;
end=id;
}
return;
}
// recursive
for (int x : adj[id]) {
if (visited[x]) continue;
prev[x]=id;
DFS(adj, x, end, level, depth, prev, visited);
}
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.