Formatted question description: https://leetcode.ca/all/590.html

590. N-ary Tree Postorder Traversal (Easy)

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?

Related Topics:
Tree

Similar Questions:

Solution 1. Recursive

// OJ: https://leetcode.com/problems/n-ary-tree-postorder-traversal/
// Time: O(N)
// Space: O(logN)
class Solution {
private:
    vector<int> ans;
    void rec(Node *root) {
        if (!root) return;
        for (auto ch : root->children) rec(ch);
        ans.push_back(root->val);
    }
public:
    vector<int> postorder(Node* root) {
        rec(root);
        return ans;
    }
};

Solution 2. Iterative

Preorder traverse the mirrored tree and reverse the result!

// OJ: https://leetcode.com/problems/n-ary-tree-postorder-traversal/
// Time: O(N)
// Space: O(logN)
class Solution {
public:
    vector<int> postorder(Node* root) {
        if (!root) return {};
        stack<Node*> s;
        s.push(root);
        vector<int> ans;
        while (s.size()) {
            root = s.top();
            s.pop();
            ans.push_back(root->val);
            for (auto c : root->children) s.push(c);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Java

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> postorder = new ArrayList<Integer>();
        Stack<Node> stack1 = new Stack<Node>();
        Stack<Node> stack2 = new Stack<Node>();
        if (root != null)
            stack1.push(root);
        while (!stack1.isEmpty()) {
            Node temp = stack1.pop();
            stack2.push(temp);
            List<Node> children = temp.children;
            int size = children.size();
            for (int i = 0; i < size; i++)
                stack1.add(children.get(i));
        }
        while (!stack2.isEmpty())
            postorder.add(stack2.pop().val);
        return postorder;
    }
}

// OJ: https://leetcode.com/problems/n-ary-tree-postorder-traversal/
// Time: O(N)
// Space: O(logN)
class Solution {
private:
    vector<int> ans;
    void rec(Node *root) {
        if (!root) return;
        for (auto ch : root->children) rec(ch);
        ans.push_back(root->val);
    }
public:
    vector<int> postorder(Node* root) {
        rec(root);
        return ans;
    }
};

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        res = []
        if not root:
            return res
        for child in root.children:
            res.extend(self.postorder(child))
        res.append(root.val)
        return res

590 - N-ary Tree Postorder Traversal

590. N-ary Tree Postorder Traversal (Easy)

Solution 1. Recursive

Solution 2. Iterative

All Problems

All Solutions