589. N叉树的前序遍历

一、589. N叉树的前序遍历 1.1、题目说明

1.2.1、递归

"""
# Definition for a Node.
class Node:
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution:
    def __init__(self) -> None:
        self.ret = []
    def preorder(self, root: 'Node') -> List[int]:
        self.preorderTraversal(root)
        return self.ret
    
    def preorderTraversal(self, root: 'Node') -> List[int]:
        if root:
            self.ret.append(root.val)
            
            if root.children:
                for child in root.children:
                    self.preorderTraversal(child)
                

1.2.2、迭代

class Solution:
    def __init__(self) -> None:
        self.ret = []

    # 使用栈 迭代
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        que = [root]
        while que:
            queSize = len(que)
            for i in range(queSize):
                node = que.pop()
                self.ret.append(node.val)
                if node.children:
                    for child in node.children[::-1]:
                        print(child.val)
                        que.append(child)
        return self.ret