N-ary Tree Level Order Traversal

Problem Id: 429 Difficulty: Medium Tag: Tree Tag: Breadth-first Search


Intuition

Basically, we could solve this problem with BFS. Please notice that, in the BFS process, we need to add another value depth to seperate nodes by their depth.

Solution


"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
from collections import deque


class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        level_order = []
        queue = deque([[root, 0]])
        while queue:
            node, depth = queue.popleft()
            if node is None:
                continue
            if len(level_order) <= depth:
                level_order.append([])
            level_order[depth].append(node.val)
            for child in node.children:
                queue.append([child, depth + 1])
        return level_order