1245

1245. Tree Diameter (Medium)

Given an undirected tree, return its diameter: the number of edges in a longest path in that tree.

The tree is given as an array of edges where edges[i] = [u, v] is a bidirectional edge between nodes u and v.  Each node has labels in the set {0, 1, ..., edges.length}.

 

Example 1:

Input: edges = [[0,1],[0,2]]
Output: 2
Explanation: 
A longest path of the tree is the path 1 - 0 - 2.

Example 2:

Input: edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
Output: 4
Explanation: 
A longest path of the tree is the path 3 - 2 - 1 - 4 - 5.

 

Constraints:

• 0 <= edges.length < 10^4
• edges[i][0] != edges[i][1]
• 0 <= edges[i][j] <= edges.length
• The given edges form an undirected tree.

Companies:
Microsoft

Related Topics:
Tree, Depth-First Search, Breadth-First Search

Similar Questions:

• Count Subtrees With Max Distance Between Cities (Hard)

Solution 1. BFS Topological Sort

// OJ: https://leetcode.com/problems/tree-diameter/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int treeDiameter(vector<vector<int>>& E) {
        int N = E.size() + 1, step = 0;
        vector<vector<int>> G(N);
        vector<int> indegree(N);
        for (auto &e : E) {
            G[e[0]].push_back(e[1]);
            G[e[1]].push_back(e[0]);
            indegree[e[0]]++;
            indegree[e[1]]++;
        }
        queue<int> q;
        for (int i = 0; i < N; ++i) {
            if (indegree[i] == 1) q.push(i);
        }
        while (q.size() > 1) {
            int cnt = q.size();
            while (cnt--) {
                int u = q.front();
                q.pop();
                --indegree[u];
                for (int v : G[u]) {
                    if (indegree[v] == 0) continue;
                    if (--indegree[v] == 1) {
                        q.push(v);
                    }
                }
            }
            ++step;
        }
        return step * 2 + q.size() - 1;
    }
};

Solution 2. Find the furthest node twice

The BFS Version:

// OJ: https://leetcode.com/problems/tree-diameter/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
    vector<vector<int>> G;
    vector<int> dist;
    int N;
    int furthest(int start) {
        queue<int> q{{start}};
        dist.assign(N + 1, INT_MAX);
        dist[start] = 0;
        int ans = 0, step = 0;
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                int u = q.front();
                q.pop();
                ans = u;
                for (int v : G[u]) {
                    if (dist[v] != INT_MAX) continue;
                    dist[v] = step + 1;
                    q.push(v);
                }
            }
            ++step;
        }
        return ans;
    }
public:
    int treeDiameter(vector<vector<int>>& E) {
        N = E.size() + 1;
        G.assign(N, {});
        for (auto &e : E) {
            G[e[0]].push_back(e[1]);
            G[e[1]].push_back(e[0]);
        }
        return dist[furthest(furthest(0))];
    }
};

The DFS Version:

// OJ: https://leetcode.com/problems/tree-diameter/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
    vector<vector<int>> G;
    vector<int> dist;
    int N;
    int dfs(int u, int level = 0) {
        if (dist[u] != INT_MAX) return u;
        dist[u] = level;
        int ans = u;
        for (int v : G[u]) {
            int f = dfs(v, level + 1);
            if (dist[f] > dist[ans]) ans = f;
        }
        return ans;
    }
    int furthest(int start, int level = 0) {
        dist.assign(N, INT_MAX);
        return dfs(start);
    }
public:
    int treeDiameter(vector<vector<int>>& E) {
        N = E.size() + 1;
        G.assign(N, {});
        for (auto &e : E) {
            G[e[0]].push_back(e[1]);
            G[e[1]].push_back(e[0]);
        }
        return dist[furthest(furthest(0))];
    }
};

Solution 3. DFS

// OJ: https://leetcode.com/problems/tree-diameter/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/tree-diameter/solution/
class Solution {
    vector<vector<int>> G;
    int N, ans = 0;
    vector<bool> seen;
    int dfs(int u) {
        seen[u] = true;
        int first = 0, second = 0;
        for (int v : G[u]) {
            if (seen[v]) continue;
            int d = 1 + dfs(v);
            if (d > first) {
                second = first;
                first = d;
            } else if (d > second) second = d;
        }
        ans = max(ans, first + second);
        return first;
    }
public:
    int treeDiameter(vector<vector<int>>& E) {
        N = E.size() + 1;
        G.assign(N, {});
        seen.assign(N, false);
        for (auto &e : E) {
            G[e[0]].push_back(e[1]);
            G[e[1]].push_back(e[0]);
        }
        dfs(0);
        return ans;
    }
};