"""
# 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, output = [root, ], []            
        while stack:
            root = stack.pop()
            output.append(root.val)
            stack.extend(root.children[::-1])
                
        return output
 
        #遞歸法
        res = []
 
        def helper(root):
            if not root:
                return 
            res.append(root.val)
            for children in root.children:
                helper(children)
        
        helper(root)
 
        return res

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
 
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
 
        #后續(xù)遍歷是先遍歷一個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn),在去遍歷這個(gè)節(jié)點(diǎn)本身
        
        #遞歸
        result = []
        def postHelper(root):
            if not root:
                return None
            children = root.children
            for child in children:
                postHelper(child)
            result.append(root.val)
 
        postHelper(root)
        return result
 
 
 
        #迭代法：輔助棧
        res = []
        stack = [root,]
 
        while stack:
            
            node = stack.pop()
            if node is not None:
                res.append(node.val)
            for children in node.children:
                stack.append(children)
        
        return res[::-1]