0559. Maximum Depth

Easy | Tree + Level-order Traversal | 40 ms (93.70%), 16 MB (46.68%)

❓ Problem Statement

Source: LeetCode - Maximum Depth of N-ary Tree GitHub: Solution / Performance

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

✍🏻 Constraints & Example

💡 Ideas

Extension question of Level-order traversal.

While traversing the tree in level order, we need to record the current level (depth).

🤖 Python3

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        # (base case)
        if not root: return 0
        if not root.children: return 1
        
        # ==================================================
        #  N-ary Tree + Level Order Traversal              =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        maxDepth = 0
        stack = [root]
        
        while stack:
            for i in range(len(stack)):
                node = stack.pop(0)
                
                for element in node.children:
                    stack.append(element)
            
            maxDepth += 1
            
        return maxDepth

🤖 Java