1. 题目描述

给定一个 n 叉树的根节点 ?root ，返回其节点值的前序遍历。
n 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]

示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

提示：
节点总数在范围?[0, 10^4]内
0 <= Node.val <= 10^4
n 叉树的高度小于或等于 1000
?
进阶：递归法很简单，你可以使用迭代法完成此题吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

????????递归思路比较简单，N 叉树的前序遍历与二叉树的前序遍历的思路和方法基本一致。

????????在前序遍历中，先遍历节点本身，然后从左向右依次前序遍历以各子节点为根的子树。对子树的遍历是以递归的方式来实现。

????????时间复杂度：O(m)，其中 m 为 N 叉树的节点数。每个节点恰好被遍历一次。

????????空间复杂度：O(m)，递归过程中需要调用栈的开销，平均情况下为 $O(log(m))$ 。但是最坏情况下树的深度为 m?1，需要O(m)的空间复杂度。

3. 代码实现

import time
from typing import List	

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

? ? ? ? 但是这道题本地测试比较麻烦。

? ? ? ? 因为输入数据是以原树的层序遍历的形式（列表）给出。而以上函数接口所接收的数据是该树的根节点。因此，首先需要将层序遍历表示转换为真正的树的表示，再输入给这个函数。感觉做这个转换比这道题目本身要难^-^。。。容我再琢磨琢磨后再补充。

? ? ? ? 此外，本题也可以用迭代的方式来实现。容我再琢磨琢磨。

本系列主目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)https://chenxiaoyuan.blog.csdn.net/article/details/123040889