🌟Simple | O(n) | C++3ms Beats 99.94% |Java 0ms Beats 100.00% |Python✅|Recursive Postorder Traversal
\n---\n# Intuition\nIn postorder traversal of an N-ary tree, we need to visit all the children of a node before visiting the node itself. This requires us to pr
##\n---\n# Intuition\nIn postorder traversal of an N-ary tree, we need to visit all the children of a node before visiting the node itself. This requires us to process each node\'s children first, and then the node itself. The problem can be solved both recursively and iteratively.\n\n# Approach\n1. **Recursive Approach** Traverse each node\'s children recursively, collect their values, and finally add the current node\'s value.\n2. **Iterative Approach** Use a stack to simulate the recursive traversal. Push the root node and its children onto the stack, process nodes by reversing the order of their children to achieve postorder traversal.\n\n# Complexity\n- **Time complexity** $$O(n)$$ where $$n$$ is the number of nodes in the tree, as each node is processed once.\n- **Space complexity** $$O(n)$$ due to the space required to store nodes in the stack or recursion stack.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> postorder(Node* root) {\n        vector<int> res;\n        traverse(root, res);\n        return res;\n    }\nprivate:\n    void traverse(Node* n, vector<int>& res) {\n        if (!n) return;\n        for (auto& c : n->children) traverse(c, res);\n        res.push_back(n->val);\n    }\n};\n```\n```java []\nclass Solution {\n    public List<Integer> postorder(Node root) {\n        List<Integer> res = new ArrayList<>();\n        traverse(root, res);\n        return res;\n    }\n    private void traverse(Node n, List<Integer> res) {\n        if (n == null) return;\n        for (Node c : n.children) traverse(c, res);\n        res.add(n.val);\n    }\n}\n```\n```python []\nclass Node:\n    def __init__(self, val=None, children=None):\n        self.val = val\n        self.children = children if children is not None else []\nclass Solution:\n    def postorder(self, root: Node) -> list[int]:\n        res = []\n        self.traverse(root, res)\n        return res\n    def traverse(self, node: Node, res: list[int]):\n        if node is None:\n            return\n        for child in node.children:\n            self.traverse(child, res)\n        res.append(node.val)\n```\n![Screenshot 2024-08-26 061628.png](https://assets.leetcode.com/users/images/35701a6f-e9ac-423f-b501-535c810e37d5_1724634398.460819.png)\n\n![image.png](https://assets.leetcode.com/users/images/c4daf289-9a2a-4c78-932a-b8ab0cc1943e_1724634360.6054492.png)\n\n---\n## **If you found this solution helpful, please upvote! \uD83D\uDE0A**\n---
['C++', 'Java', 'Python3']