题目描述

给定一棵无向树，返回它的直径：树中最长路径的 边 的数量。

树用一个数组给出，数组为 edges[i] = [u, v]，每个元素代表一条双向边连接结点 u 和 v。每个结点的编号为 {0, 1, ..., edges.length}。

样例

输入：edges = [[0,1],[0,2]]
输出：2
解释：
这棵树上最长的路径是 1 - 0 - 2，边数为 2。

输入：edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
输出：4
解释： 
这棵树上最长的路径是 3 - 2 - 1 - 4 - 5，边数为 4。

限制

• 0 <= edges.length < 10^4
• edges[i][0] != edges[i][1]
• 0 <= edges[i][j] <= edges.length
• edges 会形成一棵无向树。

算法

(深度优先遍历) $O(n)$

1. 根据边集数组建邻接表表示树。
2. 我们采用深度优先遍历的方式从 0 号点开始遍历。递归函数返回当前结点的最长路径。
3. 在遍历当前点的子结点的过程中，我们找到他们递归函数返回值加 1 的最大值和次大值。
4. 更新答案最大值加次大值，然后返回最大值。

时间复杂度

• 每个结点仅遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储邻接表。

C++ 代码

class Solution {
public:
    int ans;
    vector<vector<int>> graph;

    int dfs(int x, int fa) {
        int max1 = 0, max2 = 0;
        for (int v : graph[x])
            if (v != fa) {
                int t = dfs(v, x) + 1;
                if (max1 < t) {
                    max2 = max1;
                    max1 = t;
                } else if (max2 < t) {
                    max2 = t;
                }
            }

        ans = max(ans, (max1 + max2));
        return max1;
    }

    int treeDiameter(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        graph.resize(n);
        for (const auto &e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        ans = 0;

        dfs(0, -1);

        return ans;
    }
};