Leetcode 1665 Solution

This article provides solution to leetcode question 1665 (diameter-of-n-ary-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 1665" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/diameter-of-n-ary-tree

Solution

"""
# 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 []
"""



class Solution:
    def diameter(self, root: 'Node') -> int:
        """
        :type root: 'Node'
        :rtype: int
        """
        ans = 0
        def find(node):
            nonlocal ans



            if not node:
                return 0



            child_depths = [0, 0]
            for child_node in node.children:
                child_depths.append(find(child_node))



            child_depths.sort(key=lambda x: -x)



            ans = max(ans, child_depths[0] + child_depths[1])



            return max(child_depths) + 1



        find(root)



        return ans