"""
N-ary Tree Postorder Traversal

Given an n-ary tree, return the postorder traversal of its nodes' values.
"""

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

"""
Time: O(N)
Space: O(N)
"""
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
            for child in node.children:
                stack.append(child)
        return res[::-1]
                

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        def dfs(root):
            if not root:
                return
            for c in root.children:
                dfs(c)
            res.append(root.val)
        res = []
        dfs(root)
        return res

f9e8af863e53ac3dc7b0115a08447ba075b7d572
<mask token>


class Solution(object):
    <mask token>

<mask token>


class Solution(object):

    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """

        def dfs(root):
            if not root:
                return
            for c in root.children:
                dfs(c)
            res.append(root.val)
        res = []
        dfs(root)
        return res

<mask token>


class Solution:
    <mask token>


<mask token>


class Solution(object):

    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """

        def dfs(root):
            if not root:
                return
            for c in root.children:
                dfs(c)
            res.append(root.val)
        res = []
        dfs(root)
        return res

<mask token>


class Solution:

    def postorder(self, root: 'Node') ->List[int]:
        if not root:
            return []
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
            for child in node.children:
                stack.append(child)
        return res[::-1]


<mask token>


class Solution(object):

    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """

        def dfs(root):
            if not root:
                return
            for c in root.children:
                dfs(c)
            res.append(root.val)
        res = []
        dfs(root)
        return res

"""
N-ary Tree Postorder Traversal

Given an n-ary tree, return the postorder traversal of its nodes' values.
"""

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

"""
Time: O(N)
Space: O(N)
"""
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
            for child in node.children:
                stack.append(child)
        return res[::-1]
                

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        def dfs(root):
            if not root:
                return
            for c in root.children:
                dfs(c)
            res.append(root.val)
        res = []
        dfs(root)
        return res
