本文共 1639 字，大约阅读时间需要 5 分钟。

题目描述：

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

例如，给定一个 3叉树 :

知识点回顾：

此题考察树的前序遍历：

前序遍历：根结点、左子树结点、右子树结点

题解一： 递归法

"""# Definition for a Node.class Node(object):    def __init__(self, val=None, children=None):        self.val = val        self.children = children"""class Solution(object):    def preorder(self, root):        """        :type root: Node        :rtype: List[int]        """        result=[]        if root is None:            return []        result.append(root.val)        for node in root.children:            result.extend(self.preorder(node))        return result

题解二： 迭代法

使用进栈出栈的方法，由于栈后进先出，因此进栈的顺序与前序遍历的顺序（从左到右）相反即从右到左。

• 3.1将栈顶元素弹出至当前结点指针p
• 3.2 将p添加到result表里
• 3.3 按照从右到左的顺序将结点的孩子压入栈内。

"""# Definition for a Node.class Node(object):    def __init__(self, val=None, children=None):        self.val = val        self.children = children"""class Solution(object):    def preorder(self, root):        """        :type root: Node        :rtype: List[int]        """        if root is None:            return []                stack, result = [root, ], []                    while stack:            root = stack.pop()            result.append(root.val)            stack.extend(root.children[::-1])                        return result

时间复杂度：O(M)，其中M为树中结点的总个数。每个结点只会入栈和出栈各一次。

空间复杂度：O(M)

1.列表可包含任何数据类型的元素，单个列表中的元素无须全为同一类型。

相同：

区别：

2、.extend( )只接受一个列表作为参数，并将该参数的每个元素都添加到原有的列表中。