N-ary Tree Postorder Traversal

Problem

Given the root of 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.

Follow up: Recursive solution is trivial, could you do it iteratively?

Constraints

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 104
• The height of the n-ary tree is less than or equal to 1000.

Solution

The problem N-ary Tree Postorder Traversal can be solved using the same technique as N-ary Tree Preorder Traversal. This is based on the characteristic of traversals where the postorder traversal of a given tree is equal to the preorder traversal of a horizontally reversed tree.

Implementation

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution
{
  public:
    vector<int> postorder(Node *root)
    {
        vector<int> ret;
        if (root == NULL)
            return ret;

        stack<Node *> nodes;
        nodes.push(root);

        while (!nodes.empty())
        {
            root = nodes.top();
            nodes.pop();

            ret.push_back(root->val);
            for (auto it = root->children.begin(); it != root->children.end(); it++)
                nodes.push(*it);
        }

        reverse(ret.begin(), ret.end());
        return ret;
    }
};