Sponsored
Sponsored
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.
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).
1#include <stdio.h>
2#include <stdlib.h>
3
4struct Node {
5 int val;
6 int numChildren;
7 struct Node** children;
8};
9
10void postorderHelper(struct Node* root, int* returnSize, int* result) {
11 if (root == NULL) return;
12 for (int i = 0; i < root->numChildren; i++) {
13 postorderHelper(root->children[i], returnSize, result);
14 }
15 result[(*returnSize)++] = root->val;
16}
17
18int* postorder(struct Node* root, int* returnSize) {
19 int* result = (int*)malloc(10000 * sizeof(int));
20 *returnSize = 0;
21 postorderHelper(root, returnSize, result);
22 return result;
23}
24This 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.
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.
Time Complexity: O(n)
Space Complexity: O(n)
1#include <vector>
2#include <stack>
using namespace std;
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
vector<int> postorder(Node* root) {
vector<int> result;
if (root == nullptr) return result;
stack<Node*> stk;
stk.push(root);
while (!stk.empty()) {
Node* node = stk.top();
stk.pop();
result.insert(result.begin(), node->val);
for (Node* child : node->children) {
if (child) stk.push(child);
}
}
return result;
}
The C++ solution relies on a stack to iterate over nodes in the tree. It pushes each node onto the result list in reverse order so that the root is added last. Iterating from the root, node values are inserted at the beginning of the results list to ensure the correct postorder result after all nodes have been processed.