590. N-ary Tree Postorder Traversal

📝 Problem Details

• Title: 590. N-ary Tree Postorder Traversal
• Link: https://leetcode.com/problems/n-ary-tree-postorder-traversal/
• Difficulty: Easy
• Tags/Categories: DFS N-ary-Tree Postorder

💭What Were My Initial Thoughts?

- the problem lies with it being an n-ary tree which makes the traversal order a little more complicated
- binary tree traversal: left->right->current node
- n-ary tree traversal: each child from left to right-> current node

🤔What Did I Struggle With?

~

💡 Explanation of Solution

- recursive solution
- init an empty result vector
- for each child in the roots children
	- construct a new vector that is the result of recursive call with the child as the param
	- insert that childResult into our result vector
- push the value of the current node into the result vector
- return the result

⌛ Complexity Analysis

Time Complexity: O(n) where N nodes are traversed once
Space Complexity: O(n) due to the recursion call stack

💻 Implementation of Solution

class Solution {
 
public:
    vector<int> postorder(Node* root) {
        if(root == nullptr) return {};
        vector<int> result;
 
        for (auto& child : root->children) {
            vector<int> childResult = postorder(child);
            result.insert(result.end(), childResult.begin(), childResult.end());
        }
 
        result.push_back(root->val);    // process the current nodes value
        return result;
    }
};