Tree Diameter SOLUTION Leetcode

Tree Diameter SOLUTION Leetcode

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.

SOLUTION

Program: Tree Diameter SOLUTION in Java

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;
    }
};