589. N-ary Tree Preorder Traversal
https://leetcode.com/problems/n-ary-tree-preorder-traversal/
Given an n-ary tree, return the preorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Follow up:
Recursive solution is trivial, could you do it iteratively?
Example 1:
Input: root = [1,null,3,2,4,null,5,6] Output: [1,3,5,6,2,4]
Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]
Constraints:
- The height of the n-ary tree is less than or equal to
1000 - The total number of nodes is between
[0, 10^4]
----
Intuition
Recursive solution is trivial, just focus on iterative solution
In recursion we process the node as soon as we reach it, and then recurse on its children. We can extend the same idea here - Process node from stack as soon as you pop it, and then add its children to the stack
Takeaway
Child nodes are expected to be traversed Left to Right, so reverse the order when pushing onto the stack, so they show up in L-R order when popped out from the stack
Takeaway
Child nodes are expected to be traversed Left to Right, so reverse the order when pushing onto the stack, so they show up in L-R order when popped out from the stack
----
Time - O(n)
Space - O(h)
