Leetcode 1245: Tree Diameter

https://leetcode.com/contest/biweekly-contest-12/problems/tree-diameter/

Notes:

This is a very good question. So apparently, both DFS and BFS can be applied to solve this problem.

The naive DFS idea is we can start with any node, which is as the root of the tree, then we need to find the top 2 longest path down to the leaves. The sum of the two longest path should be the longest path. One detail is that we need to remember the prev-node, to reduce redundant traversal. The time complexity is O(N*N).

One BFS idea is very clear: start with any node A, then find the furthest node from A, call it B; then start with Node B, find the furthest Node C. Then the distance between B and C is the distance. So the time complexity is O(2*N) due to two traversals.

However, here I want to share another BFS method: from the edges to the roots, which only requires one traversal.

We need to count the indgrees of each node. Then we start with all the nodes with indegree of 1. Then layer-by-layer approaches the roots.

There may be one final node as the roots, or two nodes. If only node left, we just need to double number of layers in the BFS; otherwise, we need to add 1.

Apparently, we assume there is no loop existing in this question.

See the code below:

class Solution {
public:
    int treeDiameter(vector<vector<int>>& edges) {
        unordered_map<int, vector<int>> gh;
        unordered_map<int, int> ind;
        for(auto &a : edges) {
            gh[a[0]].push_back(a[1]);
            gh[a[1]].push_back(a[0]);
            ++ind[a[0]];
            ++ind[a[1]];
        }
        queue<int> q;
        for(auto &a : ind) {
            if(a.second == 1) {
                q.push(a.first);
                --ind[a.first];
            }
        }
        int step = 0, last = 0;
        while(q.size()) {
            int k = q.size();
            for(int i=0; i<k; ++i) {
                auto t = q.front();
                q.pop();
                for(auto &a : gh[t]) {
                    --ind[a];
                    if(ind[a] == 1) q.push(a);
                }
            }
            ++step;
            if(q.empty() && k == 2) last = 1;
        }
        return (step-1)*2 + last;
    }
};