589.md

589 N-ary Tree Preorder Traversal

Description

link

---

Solution

• N-ary Tree Traversal
• Remember to reverse the list of children for stack(first in last out)

---

Code

Complexity T : O(N) M : O(n)

"""
# 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]:
        if not root:
            return []
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            res.append(node.val)
            stack += [child for child in node.children[::-1] if child]
        return res