# 589. N-ary Tree Preorder Traversal

Easy
Given the `root` of an n-ary tree, return the preorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)
Example 1: Input: root = [1,null,3,2,4,null,5,6]
Output:
[1,3,5,6,2,4]
Example 2: Input: 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]
Output:
[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
Constraints:
• The number of nodes in the tree is in the range `[0, 104]`.
• `0 <= Node.val <= 104`
• The height of the n-ary tree is less than or equal to `1000`.
Follow up: Recursive solution is trivial, could you do it iteratively?

### 解題

Recursive
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func preorder(root *Node) []int {
res := make([]int, 0)
dfs(root, &res)
return res
}
func dfs(root *Node, arr *[]int) {
if root == nil {
return
}
*arr = append(*arr, root.Val)
for _, n := range root.Children {
dfs(n, arr)
}
}
Iterative
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func preorder(root *Node) []int {
stack := make([]*Node, 0)
res := make([]int, 0)
if root == nil {
return res
} else {
stack = append(stack, root)
}
for len(stack) != 0 {
node := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
res = append(res, node.Val)
for i:=len(node.Children) - 1; i >= 0; i-- {
stack = append(stack, node.Children[i])
}
}
return res
}