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: