Skip to content

Latest commit

 

History

History

1522.Diameter-of-N-Ary-Tree

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

1522.Diameter-of-N-Ary-Tree

本题和543.Diameter-of-Binary-Tree一样的思路。在rooted-tree里,任何路径都一定有一个最高的拐点,往左是一条以某个孩子为起点的单链,往右是另一条以某个孩子为起点单链(所谓单链就是一路向下奔向叶子节点、不带拐弯的路径)。显然,我们会取所有孩子节点里最长的两条单链。

所以本题的本质就是求以任意节点node为起点的最长单链长度h(node)。显然有递推关系:h(node) = max{h(node->child)}+1.

对于任意节点node,我们会找它孩子节点中最长的两条单链,再加1,就是以node为拐点的最长路径。全局的最长路径就是最终答案。