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
}