1245. Tree Diameter

解题思路：本题是一道图上做有记忆的dfs搜索的题目，是无向图，给定的输入是图的各个边，题目中给出一个关键信息(Each node has labels in the set {0, 1, ..., edges.length})可知图中没有环，如果是有环的图这个题是无解的。最好的证明方法就是反正法，如果有环的话标号最大的节点必然小于边的数量，例如[0, 1], [1, 2], [0, 2], 三个节点且三条边，但编号最大的节点小于边的数量。

作为一个无向不联通图，节点主要分为两种类型，一种可以称为叶节点(这个并非是官方的名字，只是我自己叫着方便)，即只有一个边与它连接，除来叶节点之外的节点则至少有两个边相连。

题目要求找出最长的一个path依次来定义这个tree的直径，很显然直径的选择是从一个叶节点到另外一个叶节点，在构建完图之后找到所有的叶节点，开始进行dfs的遍历，找出其中最长的一条路径来定义树的直径。

这个题目的模型与 568. Maximum Vacation Days 最大的不同是在计算过的值的记忆部分。

在568中每个节点的进与出的部分很清晰的分离，因此只要计算过一次，下一次递归不团从哪个节点进，都返回同样的答案。

本题则需要根据不同的输入返回不同的结果，所以memo的数据结构也不一样，对于每一个节点，需要用一个map来对应该节点到下一个节点的答案。这个地方需要使用map，而不是vector，因为需要使用到下一个节点的序号来索引。如果选择vector，无法将序号转换成下表。

时间复杂度：对于每一个节点而言，图需要计算各个出的值，复杂度为 O(e)

空间复杂度：存储每个节点到每一个方向的值 O(e)

class Solution {
public:
    int recursive(vector<vector<int>>& graph, vector<map<int, int>>& memo, vector<bool>& visited, int cur){
        int len = 0;
        for(int i = 0; i < graph[cur].size(); ++i){
            int next = graph[cur][i];
            if(!visited[next]){
                visited[next] = true;
                if(memo[cur][next] == 0){
                    memo[cur][next] = recursive(graph, memo, visited, next) + 1;
                }
                len = max(len, memo[cur][next]); 
            }
        }
        return len;
    }
    
    int treeDiameter(vector<vector<int>>& edges) {
        const int nodeCnt = edges.size() + 1;
        vector<vector<int>> graph(nodeCnt, vector<int>());
        vector<map<int, int>> memo(nodeCnt, map<int, int>());  // map<int, int>: first: the index of next node, second: the value if jump to the node
        for(auto edge : edges){
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
            memo[edge[0]][edge[1]] = 0;
            memo[edge[1]][edge[0]] = 0;
        }
        int ans = 0;
        for(int i = 0; i < graph.size(); ++i){
            if(graph[i].size() == 1){
                vector<bool> visited(nodeCnt, false);
                visited[i] = true;
                ans = max(ans, recursive(graph, memo, visited, i));
            }
        }
        return ans;
    }
};