590. N-ary Tree Postorder Traversal
1. Description
Given an n-ary tree, return the postorder 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).
2. Follow Up
Recursive solution is trivial, could you do it iteratively?
3. Example
Example 1:
Input: root = [1,null,3,2,4,null,5,6]
Output: [5,6,3,2,4,1]
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: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]
4. 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$]
5. Solutions
My Accepted Solution(Follow Up)
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
private:
vector<int> result;
void traverseNode(Node *i_root)
{
if(!i_root) return ;
for(auto child : i_root->children)
{
traverseNode(child);
}
result.push_back(i_root->val);
}
public:
// vector<int> postorder(Node* root)
vector<int> postorder(Node *i_root)
{
traverseNode(i_root);
return result;
}
};
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
// we use a stack to store a node's children
// since a stack is first in last out, so the children's order will be reversed
// for example, a node, whose value is 1, with three children [2, 3, 4]
// we push children into a stack, it will be [2, 3, 4], after pop stack, it will be [4, 3, 2]
// with the parent node, it will be [1, 4, 3, 2]
// then, we reverse the whole order, it will be [2, 3, 4, 1]
// so, the algorithm is that storing a node in to the order, using a stack to store child, when poping a child, store it
// then, reverse the whole order
class Solution
{
public:
// vector<int> postorder(Node* root)
vector<int> postorder(Node *i_root)
{
if(!i_root) return vector<int>{};
vector<int> result;
stack<Node *> parentNodes{{i_root}};
while(!parentNodes.empty())
{
auto node = parentNodes.top();
parentNodes.pop();
result.push_back(node->val);
for(auto child : node->children)
{
if(child) parentNodes.push(child);
}
}
reverse(result.begin(), result.end());
return result;
}
};