Given the root of an n-ary tree, return the postorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)
Example 1:
Input: root = [1,null,3,2,4,null,5,6] Output: [5,6,3,2,4,1]
Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]
Constraints:
[0, 104].0 <= Node.val <= 1041000.
Follow up: Recursive solution is trivial, could you do it iteratively?
This approach utilizes recursion to traverse the N-ary tree in a postorder fashion. For each node, we recursively visit all its children first before processing the node itself.
This implementation defines a helper function postorderHelper that performs the recursive traversal. The function visits each child of the current node before appending the node's value to the result array. The main function postorder initializes the result array and calls the helper function.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes, as each node is visited once.
Space Complexity: O(n) for the recursion stack in the worst case (maximum tree height).
This approach uses an iterative method to perform postorder traversal with the help of a stack to simulate recursion. Nodes are pushed onto the stack in such a way that their children are processed before the node itself.
This C solution uses a stack to hold nodes and their visitation state. Nodes are pushed onto the stack to revisit them later for value recording, ensuring that each node's children are processed before the node itself, mimicking postorder traversal.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n), where n is the number of nodes, as each node is visited once. |
| Iterative Approach with Stack | Time Complexity: O(n) |
LeetCode N-ary Tree Postorder Traversal Solution Explained - Java • Nick White • 51,096 views views
Watch 9 more video solutions →Practice N-ary Tree Postorder Traversal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor