难度: Easy
给定一个 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, 104]内0 <= Node.val <= 1041000进阶：递归法很简单，你可以使用迭代法完成此题吗?
运行时间: 28 ms
内存: 17.6 MB
"""
# 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]:
res = []
if root is None:
return res
def dfs(node: 'Node') -> None:
if node is None:
return
res.append(node.val)
for c in node.children:
dfs(c)
dfs(root)
return res
这道题使用了递归的深度优先搜索(DFS)来完成N叉树的前序遍历。首先初始化结果列表res，如果根节点为空则直接返回空列表。然后定义辅助函数dfs，传入当前节点，如果当前节点为空则直接返回。将当前节点的值加入结果列表，然后对当前节点的所有子节点递归调用dfs。最后在主函数中调用dfs，并返回结果列表res。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def preorder(self, root: 'Node') -> List[int]:
res = [] # 初始化结果列表
if root is None: # 如果根节点为空，直接返回空列表
return res
def dfs(node: 'Node') -> None:
if node is None: # 如果当前节点为空，直接返回
return
res.append(node.val) # 将当前节点的值加入结果列表
for c in node.children: # 递归遍历当前节点的所有子节点
dfs(c)
dfs(root) # 从根节点开始递归
return res # 返回结果列表
在递归函数`dfs`中进行空节点检查实际上是一种防御性编程策略。虽然根节点在主函数中已经进行了检查，但是，N叉树中的某些子节点列表可能为空或包含空节点。例如，一个节点可能显式地持有一个空引用作为其子节点之一。这种情况下，当尝试访问这个空引用的子节点时，就需要这个空检查来防止运行时错误。
在递归函数`dfs`中，子节点的遍历顺序确实影响前序遍历的结果。前序遍历的特点是先访问父节点，然后依次访问子节点。在这种情况下，子节点应当按照从左到右的顺序遍历以保持前序遍历的定义。在代码实现中，应确保子节点列表的遍历是按照这个顺序进行的，如`for c in node.children:`确保了按照列表顺序（通常是插入顺序）进行遍历。
在非递归的解决方案中，可以使用栈来模拟递归过程实现前序遍历。具体方法是，将根节点压入栈中，然后在循环中，从栈中弹出节点，记录其值，然后将其子节点从右至左压入栈中（这样可以保证左侧子节点先被弹出和访问）。这种方法的时间复杂度与递归方法相同，都是O(n)，其中n是树中的节点总数。然而，由于递归方法的函数调用可能导致调用栈溢出，使用栈的迭代方法在处理非常深的树时可能更有优势。
递归深度直接受N叉树的形状影响。在平衡的N叉树中，每个节点都有相同数量的子节点，并且每层节点数都是前一层的倍数，递归深度相对较小。例如，每个节点有3个子节点的三叉树，高度为h的树的递归深度为h。相反，在极端情况下，如链状结构（每个节点只有一个子节点），树的高度和递归深度等于节点总数，这可能导致非常深的递归调用栈。