# 1522. Diameter of N-Ary Tree
Given a root of an N-ary tree, you need to compute the length of the diameter of the tree.
The diameter of an N-ary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.
(Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.)
Example 1:
Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.
Example 2:
Input: root = [1,null,2,null,3,4,null,5,null,6]
Output: 4
Example 3:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: 7
# Solution
Approach 1: similar to diameter of a binary tree.
# Code (Python)
Approach 1: (not verified on leetcode)
class TreeNode:
def __init__(self, val, children=[]):
self.val = val
self.children = children
class Solution:
def diameterOfNaryTree(self, root: TreeNode) -> int:
if not root:
return 0
return self._diameter(root)[1]
def _diameter(self, root):
if not root.children:
return (0, 0) # (longest path passing through the root, longest path in subtree)
longest_local, longest_global = 1, 1
top_two_child_local = [0, 0]
for child in root.children:
child_local, child_global = self._diameter(child)
longest_local = max(longest_local, 1 + child_local)
if child_local >= top_two_child_local[0]:
top_two_child_local = [child_local, top_two_child_local[0]]
elif child_local >= top_two_child_local[1]:
top_two_child_local = [top_two_child_local[0], child_local]
if top_two_child_local[1] > 0: # at least two children
longest_global = max(longest_global, longest_local, child_global, 2 + sum(top_two_child_local))
else:
longest_global = max(longest_global, longest_local, child_global)
return longest_local, longest_global
node3 = TreeNode(3, [TreeNode(5)])
node4 = TreeNode(4, [TreeNode(6)])
node2 = TreeNode(2, [node3, node4])
tree1 = TreeNode(1, [node2])
print(Solution().diameterOfNaryTree(tree1))
# Code (C++)
Approach 1:
Approach 2: