// Method 1: remove leaf, similar topological sort.
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
  if (n < 2) return {0};
  vector<int> ans;
  unordered_map<int, unordered_set<int>> graph;
  for (const auto& edge : edges) {
    graph[edge[0]].insert(edge[1]);
    graph[edge[1]].insert(edge[0]);
  }
  for (const auto& [v, node] : graph) {
    if (node.size() == 1)
      ans.push_back(v);
  }
  while (!ans.empty()) {
    unordered_set<int> next;
    for (const auto& v : ans) {
      if (graph[v].size() > 0) {
        const int num = *(graph[v].begin());
        graph[num].erase(v);
        if (graph[num].size() == 1)
          next.insert(num);
        if (!graph[num].size())
          graph.erase(num);
      }
      graph.erase(v);
    }
    if (next.empty()) return ans;
    ans = vector<int>(begin(next), end(next));
  }
  return {};
}

// Method 2: diameter finding.
// Find the 1st max depth node; then use the max depth node to find the another node to find node in the longest 
// Path node; then finding the middle node.
class Solution {
 public:
  int maxDepth;
  int farthestNode;
  void dfs(int s, vector<bool> &visited, vector< vector<int> > &adj, int currDepth, vector<int> &path) {
    visited[s] = true;
    if(maxDepth < currDepth) {
      maxDepth = currDepth;
      farthestNode = s;
    }
    for(auto i : adj[s]) {
      if(!visited[i]) {
        path[i] = s;
        dfs(i, visited, adj, currDepth + 1, path);
      }
    }
  }
    
  vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    // find any leaf node and store the nodes based on the height
    // while finding the diameter of the tree
    // output the nodes with middle height
    vector< vector<int> > adj(n, vector<int>(0));
    for(int i = 0; i < edges.size(); i++) {
      adj[edges[i][0]].push_back(edges[i][1]);
      adj[edges[i][1]].push_back(edges[i][0]);
    }
        
    // resetting values  
    farthestNode = 0;
    maxDepth = 0;
    vector<int> path(n, -1);
    vector<bool> visited(n, false);
        
    // first DFS to find any leaf node
    dfs(0, visited, adj, 0, path);
        
    // resetting the values for next DFS which finds the diameter and its path
    maxDepth = -1;
    fill(visited.begin(), visited.end(), false);
    fill(path.begin(), path.end(), -1);
    dfs(farthestNode, visited, adj, 0, path);
        
    // finding the middle node by traversing the path
    int u = farthestNode;
    int currDepth = 0;
    vector<int> result;
    while(u != -1) {
      if(maxDepth % 2) {
        if(currDepth == (maxDepth / 2) || currDepth == ((maxDepth + 1) / 2)) {
          result.push_back(u);
        }
      } else {
        if(currDepth == (maxDepth / 2)) {
          result.push_back(u);
        }
      }
      currDepth++;
      u = path[u];
    }
    return result;
  }
};

// Method 3: tree DP

// DFS + BFS or (DFS + BFS)
unordered_map<int, unordered_set<int>> graph;
int max_depth_ = 0;
int node_ = -1;
int count = 0;  

void BFS(TreeNode* root, const int cur_depth, const int cur_val) {
  if (!root) return;
  if (cur_depth > max_depth_) {
    node_ = root->val;
    max_depth_ = cur_depth;
  }
  if (root->left) {
    root->left->val = count++;
    graph[root->val].insert(root->left->val);
    graph[root->left->val].insert(root->val);
    BFS(root->left, cur_depth + 1, root->left->val);
  }
  if (root->right) {
    root->right->val = count++;
    graph[root->val].insert(root->right->val);
    graph[root->right->val].insert(root->val);
    BFS(root->right, cur_depth + 1, root->right->val);
  }  
}  

int GetLongestPath(const int n, unordered_map<int, unordered_set<int>>& graph) {
  int max_len = 0;
  if (!graph.count(n)) return 0;
  for (const auto v : graph.at(n)) {
    graph[v].erase(n);
    max_len = max(GetLongestPath(v, graph), max_len);
  }
  graph.erase(n);
  return max_len + 1;
}  
  
int diameterOfBinaryTree(TreeNode* root) {
  if (!root) return 0;
  root->val = count++;
  BFS(root, 0, 1);
  return max(0, GetLongestPath(node_, graph) - 1);
}

// Tree recursive
int diameterOfBinaryTree(TreeNode* root, int& ans) {
  if(!root)
    return -1;
  const int left = diameterOfBinaryTree(root->left, ans);
  const int right = diameterOfBinaryTree(root->right, ans);
  ans = max(ans, left+right+2);
  return max(left,right)+1;
}
    
int diameterOfBinaryTree(TreeNode* root) {
  int ans=0;
  diameterOfBinaryTree(root, ans);
  return ans;
}