N-ary Tree Postorder Traversal

Leetcode Problem:

• N-ary Tree Postorder Traversal

Summary

• Postorder traversal of an n-ary tree

Approach

• Recursive approach with backtracking to traverse the tree in postorder.

Complexity

• O(N)

Explain

• The solution code uses a recursive approach with backtracking to traverse the tree in postorder
• It starts by checking if the root is null, if so, it returns an empty vector
• Then it iterates over each child of the root, recursively calls the postorder function on each child, and appends the result to the answer vector
• Finally, it appends the value of the root to the answer vector and returns the vector
• The time complexity is O(N) where N is the number of nodes in the tree.

Solution Code:

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

    Node() {}

    Node(int _val) {
        val = _val;
    }

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

class Solution {
public:
    vector postorder(Node* root) {
        if (root == nullptr) return {};
        vector ans;
        for(int i = 0 ; i < root->children.size(); i++){
            vector tmp = postorder(root->children[i]);
            ans.insert(ans.end(), tmp.begin(), tmp.end());
        }
        
        ans.push_back(root->val);
        return ans;
    }
};