解法一：递归

前序遍历就是这么定义的，不描述了。

  1. class Solution:
  2.     def preorder(self, root: 'Node') -> List[int]:
  3.         ans = []
  4.         def f(root):
  5.             if root:
  6.                 ans.append(root.val)
  7.                 for child in root.children:
  8.                     f(child)
  9.         f(root)
  10.         return ans

解法二：迭代

用一个stack来控制左右孩子的访问顺序。先访问当前节点，然后将其孩子反向压栈。这样可以保证出栈的时候，先访问的是左孩子，在访问左孩子时，左孩子的左孩子又会被压至栈顶部。直至左孩子访问完毕，栈顶会出现第一个最底层的第二左孩子。因此实现了先序遍历。

  1. class Solution:
  2.     def preorder(self, root: 'Node') -> List[int]:
  3.         ans, stack = [], [root] if root else []
  4.         while stack:
  5.             node = stack.pop()
  6.             ans.append(node.val)
  7.             stack.extend(node.children[::-1])
  8.         return ans

同类题目

144. 二叉树的前序遍历

二叉树的迭代法还可以用以下回溯方法：
先序遍历的顺序是从当前节点开始，遍历至最左叶子，之后回溯。在回溯的过程中如果出现节点有右子树，则对右子树做同样的操作。因此需要两层循环：外层负责判断调用栈是否为空；内层第一个循环将当前节点的全部左孩子按遍历顺序压入调用栈。第二个循环负责回溯，返回调用栈至第一个有右子树的节点。

  1. class Solution:
  2.     def preorderTraversal(self, root: TreeNode) -> List[int]:
  3.         ans, stack, cur = [], [root] if root else [], root
  4.         while stack:
  5.             # 迭代至最左叶子，并将访问过的节点压栈
  6.             while cur:
  7.                 stack.append(cur)
  8.                 ans.append(cur.val)
  9.                 cur = cur.left
  10.             # 回溯至第一个有右子树的节点
  11.             while stack:
  12.                 cur = stack.pop()
  13.                 if cur.right:
  14.                     break
  15.             # 将cur指向其右子树，下一次循环时对右子树实施迭代
  16.             cur = cur.right
  17.         return ans

该方法如果要改造成N叉树，则需要记录每个节点的children有哪些已经访问过了。