LeetCode-589-N叉树的前序遍历

原题链接： https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/

给定一个 N 叉树，返回其节点值的前序遍历。
例如，给定一个 3叉树 :

image.png
解题思路：

1. 递归&迭代
2. 迭代法，用栈来存储child节点，因为要顺序遍历同父节点的各个叶子节点，为满足栈的先进后出特性，将children反转后再推入stack。

"""
# 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 []
        ans = [root.val]
        if root.children:
            for child in root.children:
                ans.extend(self.preorder(child))
        return ans

"""
# 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 None
        stack = [root]
        ans = []
        while stack:
            node = stack.pop()
            ans.append(node.val)
            stack.extend(node.children[::-1])
        return ans