Python | Depth-First Search | DFS
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def postorder(self, root: \'Node\') -> List[int]:\n        if not root:\n  
[see the Successfully Accepted Submission](https://leetcode.com/problems/n-ary-tree-postorder-traversal/submissions/1368477504/?envType=daily-question&envId=2024-08-26)\n\n# Code\n```python3 []\nclass Solution:\n    def postorder(self, root: \'Node\') -> List[int]:\n        if not root:\n            return []\n        \n        stack = [root]\n        output = []\n        \n        while stack:\n            node = stack.pop()\n            output.append(node.val)\n            # Add children to stack if they exist\n            if node.children:\n                stack.extend(node.children)\n        \n        # Since the nodes were added in root-first order, we reverse the output for postorder\n        return output[::-1]\n\n```\n\n# Postorder Traversal\n\nIn postorder traversal, we visit the children of a node before visiting the node itself. For an n-ary tree, the steps are:\n\n1. Traverse all the children nodes of the current node.\n2. Visit the current node.\n\n### Example\n\nGiven the tree:\n\n```\n       1\n     / | \\\n    3  2  4\n   / \\\n  5   6\n\n\n```\n\n\nThe postorder traversal would be `[5, 6, 3, 2, 4, 1]`.\n\n## Recursive Solution\n\nA recursive solution is straightforward but doesn\'t meet the problem\'s requirement for an iterative solution. Here\'s how we can do it iteratively:\n\n## Iterative Solution Approach\n\nTo perform the postorder traversal iteratively:\n\n1. We can use a stack to simulate the recursive call stack.\n2. We push the nodes onto the stack in a manner such that when we pop them, we get the postorder sequence.\n3. We push the root node and process it by pushing its children to the stack.\n4. We reverse the result to ensure the correct postorder sequence because during processing, the root will come first, followed by its children.\n\n## Explanation\n\n- **Stack Initialization:** We start with the root node on the stack.\n- **Traversal Loop:** We pop nodes from the stack, add their values to the output list, and then push their children onto the stack.\n- **Postorder Adjustment:** Because we added nodes to the output in the reverse of postorder (root first, then children), we reverse the `output` list at the end to get the correct postorder sequence.\n\n## Time Complexity\n\nThe time complexity is \\(O(N)\\), where \\(N\\) is the number of nodes, as we visit each node exactly once.\n\n## Space Complexity\n\nThe space complexity is also \\(O(N)\\), primarily due to the stack that can hold all nodes in the worst case.\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)\n\n
['Python3']