N-ary Tree Postorder Traversal

Problem

• Given the root of an n-ary tree, return the postorder traversal of its nodes' values.

Reflections

Memorized at this point. For the record I am not merely copying the dfs func from previous challenges. I am rewriting it each time.

Go Solution

func postorder(root *Node) []int {
    var res []int
    var dfs func(node *Node)
    dfs = func(node *Node) {
        if node == nil {
            return
        }

        for _,child := range(node.Children) {
            dfs(child)
        }
        res = append(res, node.Val)
    }
    dfs(root)
    return res
}

Performance

• Runtime beats: 100%
• Memory beats: 78.67%

Complexity

• Time: O(n)
• Space: O(n + h) - h is height of tree, if its nothing more than a degenerate linked list