589 N-ary Tree Preorder Traversal

1. Description

Given the root of an n-ary tree, return the preorder traversal of its nodes' values. Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value.

 

constraints :

• The number of nodes in the tree is in the range [0, \(10^{4}\)].
• 0 <= Node.val <= \(10^{4}\)
• The height of the n-ary tree is less than or equal to 1000.

 

2. Algorithms

Preorder algorithm traverse tree below way :

• Visit the root.
• Traverse the left subree.
• Traverse the right subtree.

 

Because our node have multiple nodes in one level, we have to use for loop to interate all nodes in current level.

3. Codes

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

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        def traversePreorder(root, res) : 
            if root : 
                res.append(root.val) 
                for child in root.children : 
                    traversePreorder(child, res) 
            return res 
        return traversePreorder(root, [])

4. Conclusion