N Ary Tree Preorder Traversal

N叉树的前序遍历

题目描述

给定一个N叉树，返回其节点值的前序遍历。

解法

N叉树的定义为：

type Node struct {
    Val int
    Children []*Node
}

解法一：递归

• 时间复杂度：O(n)

• 空间复杂度：O(n)

func preorder(root *Node) []int {
    result := []int{}
    if root == nil {
        return result
    }
    result = append(result, root.Val)
    for _, v := range root.Children {
        result = append(result, preorder(v)...)
    }
    return result
}

解法二：迭代

• 时间复杂度：O(n)

• 空间复杂度：O(n)

func preorder(root *Node) []int {
    result := []int{}
    if root == nil {
        return result
    }
    stack := []*Node{root}
    for len(stack) > 0 {
        index := len(stack) - 1
        root = stack[index]
        stack = stack[:index]

        result = append(result, root.Val)
        for i := len(root.Children) - 1; i >= 0; i-- {
            if root.Children[i] != nil {
                stack = append(stack, root.Children[i])
            }
        }
    }
    return result
}