LeetCode #590 N-ary Tree Postorder Traversal
Problem
Given an n-ary tree, return the postorder traversal of its nodes’ values.
For example, given a 3-ary tree:
Return its postorder traversal as: [5,6,3,2,4,1].
Note: Recursive solution is trivial, could you do it iteratively?
Solution — Recursion
As problem describes, it’s trivial.
Complexity
Because each node will be traversed once, it’s time complexity is O(n) if n denotes to counts of nodes in this tree.
The deepest calling stack size will reach the deepest path length in this tree. Hence, it’s space complexity will be O(h) if h denotes to the deepest path length from root to leaf in this tree. Or it can be O(logn) because h is bounded by logn.
Solution — Iteration
Use a stack for saving every met child and record it after popped out. And reverse entire result list as the answer.
Complexity
Each node will be visited once so it’s time complexity is O(n) if n denotes to counts of nodes in this tree.
For space complexity, this stack should have ability to store all nodes with their siblings whose size will no more than N-1 in the deepest path of this tree. So it uses O(h) extra space if h denotes to the length of the deepest path from root to leaf of this tree. Or it can be O(logn) because h is bounded by logn.
