LeetCode #559 Maximum Depth of N-ary Tree

Posted on | Post modified | In , , , , , ,

Problem

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.

Example

img

We should return its max depth, which is 3.

Solution

Method: Depth-first Search

Time Complexity: O(n)

Space Complexity: O(depth of tree)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if not root:
            return 0
        
        stack = [(1, root)]
        ret = 1
    
        while stack:
            level, node = stack.pop()
            
            if node.children:
                for child in node.children:
                    if child:
                        stack.append((level + 1, child))
                        if level + 1 > ret:
                            ret = level + 1
        
        return ret

Boundary Condition

  • What should I return when the input is empty? Level 0 or Level 1?