/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {
children = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
children = new ArrayList<Node>();
}
public Node(int _val,ArrayList<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
// find lowest common ancestor with longest path
// simple recursion
int res = 0;
public int diameter(Node root) {
height(root);
return res;
}
// max height
int height(Node node) {
if(node==null) return 0;
int max1 = 0, max2 = 0;
for(Node temp : node.children) {
int val = height(temp) +1;
if(val >= max1) {
max2 = max1;
max1 = val;
} else if(val > max2) {
max2 = val;
}
}
res = Math.max(res, max1+max2);
return max1;
}
}