N Ary Tree Postorder Traversal

N`叉树的后序遍历

题目描述

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

解法

N叉树的定义为：

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

解法一：递归

• 时间复杂度：O(n)

• 空间复杂度：O(n)

func postorder(root *Node) []int {
    result := []int{}
    if root == nil {
        return result
    }
    for i := 0; i < len(root.Children); i++ {
        result = append(result, postorder(root.Children[i])...)
    }
    result = append(result, root.Val)
    return result
}

解法二：迭代法：

• 时间复杂度：O(n)

• 空间复杂度：O(n)

func postorder(root *Node) []int {
    result := []int{}
    if root == nil {
        return result
    }

    stack1 := []*Node{root}
    stack2 := []int{}
    for len(stack1) > 0 {
        index := len(stack1) - 1
        root := stack1[index]
        stack1 = stack1[:index]

        stack2 = append(stack2, root.Val)
        for i := 0; i < len(root.Children); i++ {
            if root.Children[i] != nil {
                stack1 = append(stack1, root.Children[i])
            }
        }
    }

    for i := len(stack2) - 1; i >= 0; i-- {
        result = append(result, stack2[i])
    }
    return result
}