"""# Definition for a Node.class Node: def __init__(self, val=None, children=None): self.val = val self.children = children if children is not None else []"""classSolution:defdiameter(self,root:'Node')->int:""" :type root: 'Node' :rtype: int """defdfs(root):ifrootisNone:return0nonlocalansm1=m2=0forchildinroot.children:t=dfs(child)ift>m1:m2,m1=m1,telift>m2:m2=tans=max(ans,m1+m2)return1+m1ans=0dfs(root)returnans
/*// 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; }};*/classSolution{privateintans;publicintdiameter(Noderoot){ans=0;dfs(root);returnans;}privateintdfs(Noderoot){if(root==null){return0;}intm1=0,m2=0;for(Nodechild:root.children){intt=dfs(child);if(t>m1){m2=m1;m1=t;}elseif(t>m2){m2=t;}}ans=Math.max(ans,m1+m2);return1+m1;}}
/** * Definition for a Node. * type Node struct { * Val int * Children []*Node * } */funcdiameter(root*Node)int{ans:=0vardfsfunc(root*Node)intdfs=func(root*Node)int{ifroot==nil{return0}m1,m2:=0,0for_,child:=rangeroot.Children{t:=dfs(child)ift>m1{m2,m1=m1,t}elseift>m2{m2=t}}ans=max(ans,m1+m2)return1+m1}dfs(root)returnans}
"""# Definition for a Node.class Node: def __init__(self, val=None, children=None): self.val = val self.children = children if children is not None else []"""classSolution:defdiameter(self,root:'Node')->int:""" :type root: 'Node' :rtype: int """defbuild(root):nonlocaldifrootisNone:returnforchildinroot.children:d[root].add(child)d[child].add(root)build(child)defdfs(u,t):nonlocalans,vis,d,nextifuinvis:returnvis.add(u)forvind[u]:dfs(v,t+1)ifans<t:ans=tnext=ud=defaultdict(set)vis=set()build(root)ans=0next=Nonedfs(root,0)vis.clear()dfs(next,0)returnans
/*// 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; }};*/classSolution{privateMap<Node,Set<Node>>g;privateSet<Node>vis;privateNodenext;privateintans;publicintdiameter(Noderoot){g=newHashMap<>();build(root);vis=newHashSet<>();next=root;ans=0;dfs(next,0);vis.clear();dfs(next,0);returnans;}privatevoiddfs(Nodeu,intt){if(vis.contains(u)){return;}vis.add(u);if(t>ans){ans=t;next=u;}if(g.containsKey(u)){for(Nodev:g.get(u)){dfs(v,t+1);}}}privatevoidbuild(Noderoot){if(root==null){return;}for(Nodechild:root.children){g.computeIfAbsent(root,k->newHashSet<>()).add(child);g.computeIfAbsent(child,k->newHashSet<>()).add(root);build(child);}}}
/** * Definition for a Node. * type Node struct { * Val int * Children []*Node * } */funcdiameter(root*Node)int{g:=make(map[*Node][]*Node)vis:=make(map[*Node]bool)next:=rootans:=0varbuildfunc(root*Node)build=func(root*Node){ifroot==nil{return}for_,child:=rangeroot.Children{g[root]=append(g[root],child)g[child]=append(g[child],root)build(child)}}build(root)vardfsfunc(u*Node,tint)dfs=func(u*Node,tint){ifvis[u]{return}vis[u]=trueift>ans{ans=tnext=u}ifvs,ok:=g[u];ok{for_,v:=rangevs{dfs(v,t+1)}}}dfs(next,0)vis=make(map[*Node]bool)dfs(next,0)returnans}