# 1245. Tree Diameter

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { public: int treeDiameter(vector>& edges) { const int n = edges.size(); int ans = 0; vector> tree(n + 1); for (const vector& edge : edges) { const int u = edge[0]; const int v = edge[1]; tree[u].push_back(v); tree[v].push_back(u); } maxDepth(tree, 0, -1, ans); return ans; } private: int maxDepth(const vector>& tree, int u, int parent, int& ans) { int maxDepth1 = 0; // The max depth int maxDepth2 = -1; // The 2nd max depth for (const int v : tree[u]) { if (v == parent) continue; const int depth = maxDepth(tree, v, u, ans); if (depth > maxDepth1) { maxDepth2 = maxDepth1; maxDepth1 = depth; } else if (depth > maxDepth2) { maxDepth2 = depth; } } ans = max(ans, maxDepth1 + maxDepth2); return 1 + maxDepth1; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public int treeDiameter(int[][] edges) { final int n = edges.length; List[] tree = new List[n + 1]; for (int i = 0; i < tree.length; ++i) tree[i] = new ArrayList<>(); for (int[] edge : edges) { final int u = edge[0]; final int v = edge[1]; tree[u].add(v); tree[v].add(u); } maxDepth(tree, 0, -1); return ans; } private int ans = 0; private int maxDepth(List[] tree, int u, int parent) { int maxDepth1 = 0; // The max depth int maxDepth2 = -1; // The 2nd max depth for (final int v : tree[u]) { if (v == parent) continue; final int depth = maxDepth(tree, v, u); if (depth > maxDepth1) { maxDepth2 = maxDepth1; maxDepth1 = depth; } else if (depth > maxDepth2) { maxDepth2 = depth; } } ans = Math.max(ans, maxDepth1 + maxDepth2); return 1 + maxDepth1; } }