N叉樹的三種遍歷(層次遍歷、前序遍歷、後序遍歷)

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
 
class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []
 
        queue = collections.deque()
        queue.append(root)
        res = []
 
        while queue:
            size = len(queue)
            temp = []
            for _ in range(size):
                node = queue.popleft()
                temp.append(node.val)
                if node.children:
                    queue.extend(node.children)
            res.append(temp)
        
        return res

"""
# 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 []
 
        #後續遍歷是先遍歷一個節點的孩子節點,在去遍歷這個節點本身
        
        #遞迴
        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]