MUYANG GUO / INDEX

LeetCode

LeetCode 1522 Diameter Of N-Ary Tree - Medium

1522. Diameter of N-Ary Tree -- Medium

·1 min read·#LeetCode#Medium#Python

1522. Diameter Of N-Ary Tree — Medium

Open on LeetCode

Problem

  1. Diameter of N-Ary Tree -- Medium

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

Constraints:

The depth of the n-ary tree is less than or equal to 1000. The total number of nodes is between [0, 10^4].

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:
        self.res = 0
        self.getHeight(root)
        return self.res
    def getHeight(self, node):
        if not node:
            return 0
        max_1 = 0
        max_2 = 0
        for child in node.children:
            parentHeight = self.getHeight(child) + 1
            if parentHeight > max_1:
                max_1, max_2 = parentHeight, max_1
            elif parentHeight > max_2:
                max_2 = parentHeight
        depth = max_1 + max_2
        self.res = max(self.res, depth)
        return max_1

Comments