1245. Tree Diameter

1245. Tree Diameter

Description

The diameter of a tree is the number of edges in the longest path in that tree.

There is an undirected tree of n nodes labeled from 0 to n - 1. You are given a 2D array edges where edges.length == n - 1 and edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i in the tree.

Return the diameter of the tree.

Example 1:

Input: edges = [[0,1],[0,2]]
Output: 2
Explanation: The 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: The longest path of the tree is the path 3 - 2 - 1 - 4 - 5.

Constraints:

• n == edges.length + 1
• 1 <= n <= 10^4
• 0 <= a_i, b_i < n
• a_i != b_i

Hints/Notes

• binary tree, tree dp

Solution

Language: C++

class Solution {
public:
    int res = 0;
    vector<vector<int>> graph;

    int treeDiameter(vector<vector<int>>& edges) {
        if (edges.empty()) {
            return 0;
        }
        graph.resize(edges.size() + 1, vector<int>());
        build(edges);
        traverse(0, -1);
        return res;
    }

    int traverse(int root, int prev) {
        int mx = 0, mx2 = 0;
        for (int u : graph[root]) {
            if (u == prev) {
                continue;
            }
            int depth = traverse(u, root) + 1;
            if (depth > mx) {
                mx2 = mx;
                mx = depth;
            } else if (depth > mx2) {
                mx2 = depth;
            }
        }
        res = max(res, mx + mx2);
        return mx;
    }

    void build(vector<vector<int>>& edges) {
        for (auto e : edges) {
            int u = e[0];
            int v = e[1];
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
    }
};