LeetCode #589 N-ary Tree Preorder Traversal
Problem
Given an n-ary tree, return the preorder traversal of its nodes’ values.
For example, given a 3-ary tree:
Return its preorder traversal as: [1,3,5,6,2,4].
Note: Recursive solution is trivial, could you do it iteratively?
Solution — Recursion
As problem describes, it’s trivial.
Complexity
Because each node is traversed once, it’s time complexity is O(n) if n denotes to counts of nodes in this tree. And it’s space complexity will be O(h) if h denotes to the longest path length from root to leaf in this tree. Or you can say O(logn) because h is bounded by logn.
Solution — Iteration
Use a stack for saving children whose parent has been visited.
Complexity
Actually it’s the same as using call stack in recursion approach. Therefore, it’s time and space complexity will be O(n) and O(h) (or O(logn)) correspondingly.
